Pythonでバイナリツリーのインオーダートラバーサルを実行するプログラム

二分木があるとしましょう。ルートのインオーダートラバーサルをリストとして含むリストを見つける必要があります。私たちが知っているように、順序のないトラバーサルは、ツリー内のすべてのノードをトラバースする方法です-

• 左側のサブツリーを再帰的にトラバースします。

• 現在のノードをトラバースします。

• 右のサブツリーを再帰的にトラバースします。

この問題を繰り返し解決する必要があります。

したがって、入力が次のような場合

その場合、出力は[12,13,4,16,7,14,22]

これを解決するには、次の手順に従います-

• inorder：=新しいリスト

• スタック：=空のスタック

• 次のことを無限に行います。

  • ルートがnullでない場合、

    • ルートをスタックにプッシュします

    • ルート：=ルートの左側

  • それ以外の場合、スタックが空でない場合は

    • ルート：=スタックの最上位要素とスタックからのポップ

    • 順序の最後にルートの値を挿入します

    • ルート：=ルートの右

  • それ以外の場合

    • ループから出てきます

• 順番に戻る

理解を深めるために、次の実装を見てみましょう-

例

class TreeNode:
   def __init__(self, value):
      self.val = value
      self.left = None
      self.right = None
class Solution:
   def solve(self, root):
      inorder = []
      stack = []
      while True:
         if root:
            stack.append(root)
            root = root.left
         elif stack:
            root = stack.pop()
            inorder.append(root.val)
            root = root.right
         else:
            break
      return inorder

ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
print(ob.solve(root))

入力

root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)

出力

[12, 13, 4, 16, 7, 14, 22]