Trees

二分木は、各ノードが「値」と「左の子」「右の子」を持つ構造。リストが一直線だったのに対し、木は枝分かれする。

このグループの型は再帰。子もまた木なので、「木を処理する」は「このノード1つ分を処理して、左と右に同じことを頼む」に必ず分解できる。書くことは毎回3つだけ——止まる条件 / 1ノード分の仕事 / 子に同じ関数を呼ぶ。

Invert Binary Tree

https://neetcode.io/problems/invert-a-binary-tree/question?list=blind75

木を左右に鏡写しにする。

    1              1
   / \            / \
  2   3    ->    3   2
 / \ / \        / \ / \
4  5 6  7      7  6 5  4

全体を一度に裏返そうとすると手が止まる。1ノード分の仕事は「自分の左の子と右の子を入れ替える」だけで、残りは子に同じことを頼めばいい。

class Solution {
    // 例: [1,2,3,4,5,6,7]  ->  [1,3,2,7,6,5,4]
    invertTree(root: TreeNode | null): TreeNode | null {
        // ① 止まる条件: 空の木は裏返しても空
        if (!root) return null;

        // ② 1ノード分の仕事: 左右を入れ替える。
        //    先に左を退避しないと、1行目の代入で左が消えて右が2つになる（18 と同じ罠）
        const left = root.left;
        root.left = root.right;
        root.right = left;

        // ③ 子に同じことを頼む。子もまた木なので、同じ関数がそのまま使える
        this.invertTree(root.left);
        this.invertTree(root.right);

        return root;
    }
}

全ノードを1回ずつ触るので時間 O(n)。空間は再帰の深さぶんで O(h)（h は木の高さ。一直線の木だと最悪 O(n)）。

• 入れ替えるのは矢印だけ。2 の枝の中身（4, 5）は何もしないまま右へ移り、そのあと 2 自身の番で中が裏返る
• ②と③は逆順でもいい。先に子を裏返してから自分を入れ替えても、各ノードがちょうど1回入れ替わる点は変わらない

応用: 木の問題は**「止まる条件 / 1ノード分の仕事 / 子に同じ関数を呼ぶ」の3つを埋める**だけ。全体を一度に考えないのがコツ。