Pythonで方向リストを使って二分木を走査するプログラム

二分木と、"R"（右）、"L"（左）、"U"（上）からなる文字列のリスト moves が与えられているとします。ルートから出発し、moves の各指示に従って木をたどります。"R" は右の子ノードへ移動、"L" は左の子ノードへ移動、"U" は親ノードへ戻ることを意味します。

例えば、次のような二分木があったとします。

入力が ["R", "R", "U", "L"] の場合、出力は 3 になります。

解決のアプローチ

この問題は、通過したノードの履歴をスタック（リスト）で管理することで解決できます。手順は以下の通りです。

• 空のリスト past を用意します。
• moves 内の各移動指示に対して、以下を繰り返します。
  • まず現在のノードを past の末尾に追加します。
  • 移動が "L" の場合は、現在のノードを左の子ノードに更新します。
  • 移動が "R" の場合は、現在のノードを右の子ノードに更新します。
  • それ以外（"U" の場合）は、past の末尾要素を削除し、その新しい末尾の要素を取り出して現在のノードとします。
• 最終的に、現在のノードの値を返します。

ポイントは、"U"（上へ戻る）操作が来る前に必ず現在のノードを past に記録しておくことです。こうすることで、親へ戻る際に履歴から正しく前のノードを復元できます。

実装例

以下のコードで実際の動作を確認してみましょう。

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

class Solution:
    def solve(self, root, moves):
        past = []
        for move in moves:
            past.append(root)
            if move == "L":
                root = root.left
            elif move == "R":
                root = root.right
            else:
                past.pop()
                root = past.pop()
        return root.val

ob = Solution()
root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
traverse = ["R","R","U","L"]
print(ob.solve(root, traverse))

入力

root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
["R","R","U","L"]

出力

3

処理の流れを詳しく見る

入力 ["R", "R", "U", "L"] の場合の動作を追跡すると、次のようになります。

1. 最初の "R"：ノード2から右の子ノード4へ移動します。
2. 次の "R"：ノード4から右の子ノード5へ移動します。
3. 次の "U"：履歴をたどって親ノード4へ戻ります。
4. 最後の "L"：ノード4から左の子ノード3へ移動します。

結果として、最終的なノードの値である 3 が出力されます。このアルゴリズムの計算量は O(n)（n は moves の長さ）、必要な記憶領域も O(n) であり、非常に効率的な解法です。