バイナリツリー_インオーダー走査(Inorder Traversal)の実装　#442

バイナリツリーの走査方法に関するまとめ第2弾です。
バイナリツリーについて別で2本記事を書いています。

走査とは先頭から順にデータを見ていくことを指し、バイナリツリーを走査するアルゴリズムは主に４つあります。

Pre-order Traversal
In-order Traversal
Post-order Traversal
Level-order Traversal

このうちのIn-order Traversalについてです。

インオーダー走査とは

インオーダー走査は、バイナリツリーを巡る方法の一つで、ノードを「左->ルート->右」の順序で訪問します。この走査方法は、特にバイナリサーチツリーにおいて、ノードを昇順でアクセスするのに役立ちます。

1. 左サブツリーを走査する

2. 左側に移動できなくなったらルートノードを訪問してデータ出力

3. 右サブツリーを走査する

ブログに分かりやすい図がありました。

うさぎでも分かる2分探索木

具体的なコード例

探索結果をresultに格納していき、最後に出力するようにしています。
まず自分で以下のように書いてみました。

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode], result=None) -> List[int]:
        if result == None:
            result = []
        
        if root:        
            if root.left:
                self.inorderTraversal(root.left, result)

            result.append(root.val)

            if root.right:
                self.inorderTraversal(root.right, result)
        
        return result

少し無駄がありそうだなと思ったのですが、参考ブログに良いヒントがあり、以下のようにリファクタしました。

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        def _inorder(root, result):
            if root:
                _inorder(root.left, result)
                result.append(root.val)
                _inorder(root.right, result)
            return result
        
        return _inorder(root, result)

ここまでお読みいただきありがとうございました！

参考

うさぎでもわかる2分探索木　後編　2分探索木における4つの走査方法