pythonで深さ優先探索の行きがけ、帰りがけ、通りがけの使い分け

深さ優先探索では、行きがけ（preorder）、帰りがけ（postorder）、通りがけ（inorder）を使い分けることがあるが、こんがらってしまう。

理解しやすいよう2分木で簡単な実装をしてみた。以下、当該ノード、左部分技、右部分技のことを、それぞれ自分、左、右と略して書く。

2分木

この記事では2分木を以下のように定義する。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

自分から次に行く時に処理するイメージ。自分→左→右の順。

def dfs(node):
    if not node:
        return
            
    my_function()
    
    dfs(node.left)
    dfs(node.right)

自分に帰ってきた時に処理するイメージ。左→右→自分の順。

def dfs(node):
    if not node:
        return
                
    dfs(node.left)
    dfs(node.right)

    my_function()

左から自分を通って右に行く時に自分を処理するイメージ。左→自分→右の順。

def dfs(node):
    if not node:
        return
                
    dfs(node.left)

    my_function()

    dfs(node.right)

イメージがついたらあとは練習。LeetCodeにそのまんまの問題がある。