二分木

二分木(binary tree)は、全ての節点において子が2個以下である木構造。

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

二分木の走査

二分木の走査は、以下の4つの走査方法がある。

先行順：　節点、左部分木、右部分木の順に走査する。
中間順：　左部分木、節点、右部分木の順に走査する。
後行順：　左部分木、右部分木、節点の順に走査する。
幅優先探索：　木を1階層ずつ走査する。

先行順、中間順、後行順の違いは節点の走査順にあり、
節点を左右より先に走査するのは先行順、左右の中間で走査するのは中間順、左右より後に走査するのは後行順となる。
それぞれの操作方法を実現するには、回帰と反復のアルゴリズムがある。

回帰アルゴリズム

先行順

class Solution:
    def preorder_traversal(self, root: Optional[TreeNode]) -> List[int]:
        def preorder(node: Optional[TreeNode]):
            # 再帰の終了条件 (leaf node)
            if node is None:
                return
            # 節点の処理
            ans.append(node.val)
            # 左部分木の処理
            preorder(node.left)
            # 右部分木の処理
            preorder(node.right)

        ans = []
        preorder(root)
        return ans

中間順

class Solution:
    def inorder_traversal(self, root: Optional[TreeNode]) -> List[int]:
        def inorder(node: Optional[TreeNode]):
            # 再帰の終了条件 (leaf node)
            if node is None:
                return
            # 左部分木の処理
            inorder(node.left)
            # 節点の処理
            ans.append(node.val)
            # 右部分木の処理
            inorder(node.right)

        ans = []
        inorder(root)
        return ans

後行順

class Solution:
    def postorder_traversal(self, root: Optional[TreeNode]) -> List[int]:
        def postorder(node: Optional[TreeNode]):
            # 再帰の終了条件 (leaf node)
            if node is None:
                return
            # 左部分木の処理
            postorder(node.left)
            # 右部分木の処理
            postorder(node.right)
            # 節点の処理
            ans.append(node.val)

        ans = []
        postorder(root)
        return ans

反復アルゴリズム

先行順

class Solution:
    def preorder_traversal(self, root: TreeNode) -> List[int]:
        ans = []
        if not root:
            return ans

        stack = [root]
        while stack:
            node = stack.pop()
            # 節点の処理
            ans.append(node.val)
            if node.right:
                # 右の子をスタックに追加
                stack.append(node.right)
            if node.left:
                # 左の子をスタックに追加
                stack.append(node.left)

        return ans

中間順

class Solution:
    def inorder_traversal(self, root: TreeNode) -> List[int]:
        ans = []
        if not root:
            return ans

        stack = []
        node = root
        while stack or node:
            if node:
                # 左部分木を最後までたどり、たどる順でstackに積む
                stack.append(node)
                node = node.left
            else:
                # 左部分木の最後までたどったら、stackから取り出してansに追加
                node = stack.pop()
                ans.append(node.val)
                # 右部分木をたどる
                node = node.right

        return ans

後行順

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        ans = []
        if not root:
            return ans

        stack = [root]
        while stack:
            node = stack.pop()
            # 節点の処理
            ans.append(node.val)
            if node.left:
                # 右の子をスタックに追加
                stack.append(node.left)
            if node.right:
                # 左の子をスタックに追加
                stack.append(node.right)

        return ans[::-1]

幅優先探索

class Solution:
    def level_order(self, root: Optional[TreeNode]) -> List[List[int]]:
        ans = []
        if not root:
            return ans

        queue = [root]
        while queue:
            # 現在階層のノード数を取得
            size = len(queue)
            cur_level = []

            for i in range(size):
                node = queue.pop(0)
                cur_level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            ans.append(cur_level)

        return ans

leetcode問題集