よわよわエンジニアが解く226. Invert Binary Tree

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        
        root.left , root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

このように解くらしい。
全くわからなかったため、再帰処理から学ぶことにした。

再帰処理とは、、自分自身を呼び出す処理が含まれる関数。終了条件を書かないと大変なことになる。
処理結果は終端から積み上げる。

以下は1からnまでの整数を合計する処理。０が返されると前の関数に戻り、計算結果が積み上げられていく。

def total(n):
    if n < 1:
        return 0
    return n + total(n - 1)

print(total(5))
# 5 + total(4) 10が返されるので10+5
# 4 + total(3) 6が返されるので6+4
# 3 + total(2) 3が返されるので3+3
# 2 + total(1) 1が返されるので1+2
# 1 + total(0) 0が返されるので0+1
# 0

以下はnの階乗を求める処理。1が返されると前の関数に戻り、計算結果が積み上げられていく。
0を返すと0になるので注意。

def factorial(n):
    if n < 1:
        return 1
    return n * factorial(n - 1)

print(factorial(3))
# 3 * total(2) 2が返されるので3*2
# 2 * total(1) 1が返されるので2*1
# 1 * total(0) 1が返されるので1*1
# 0

上記を踏まえて考えると、入力が[4,2,7,1,3,6,9]の場合の処理の流れは、
ルートノード(4): 左右の子ノードを反転（左: 7, 右: 2）し、再帰的に左右の子ノードに対して処理を行う。
左子ノード(7): 左右の子ノードを反転（左: 9, 右: 6）。9と6に対して再帰処理を行うが、両方とも子ノードがない（None）ため、そのまま戻る。
右子ノード(2): 左右の子ノードを反転（左: 3, 右: 1）。3と1に対して再帰処理を行うが、これらも両方子ノードがない（None）ため、そのまま戻る。

再帰関数では一度実行した処理が再度実行されることはない。
9と6の再帰処理から７のノードに戻った時に、もう一度左から見にいくことはないため、全てのノードを走破できる。

    4
   / \
  7   2
 / \ / \
9  6 3 1

例えば以下のような探索処理があった場合は、左端まで探して上のノードに戻った時に、また左端から探すということは行わず、右の子ノードを探しにいく。

left_result = find_node(root.left, value)
if left_result is not None:
    return left_result

return find_node(root.right, value)