Pythonで二分木レベルを交互にトラバースするプログラム

二分木があるとすると、左から右、右から左に交互に各レベルの値を表示する必要があります。

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

その場合、出力は[5、-10、4、-2、-7、15]

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

• ルートがnullの場合、

  • 新しいリストを返す

• s1：=リストは最初にルートを挿入します

• s2：=新しいリスト

• res：=新しいリスト

• s1が空でないか、s2が空でない場合は、実行してください

  • s1が空でない間、実行します

    • node：=s1から最後の要素を削除する

    • ノードの左側がnullでない場合、

      • s2の最後にノードの左側を挿入します

    • ノードの権利がnullでない場合、

      • s2の最後にノードの右側を挿入します

    • resの最後にノードの値を挿入します

  • s2が空でない間は、実行してください

    • node：=s2から最後の要素を削除する

    • ノードの権利がnullでない場合、

      • s1の最後にノードの右側を挿入します

    • ノードの左側が空でない場合、

      • s1の最後にノードの左側を挿入します

    • resの最後にノードの値を挿入します

• 解像度を返す

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

例

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):
      if not root:
         return []
      s1 = [root]
      s2 = []
      res = []
      while s1 or s2:
         while s1:
            node = s1.pop()
            if node.left:
               s2.append(node.left)
            if node.right:
               s2.append(node.right)
            res.append(node.val)
         while s2:
            node = s2.pop()
            if node.right:
               s1.append(node.right)
            if node.left:
               s1.append(node.left)
            res.append(node.val)
      return res

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(-10)
root.left.left = TreeNode(-2)
root.right.left = TreeNode(-7)
root.right.right = TreeNode(15)
print(ob.solve(root))

入力

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(-10)
root.left.left = TreeNode(-2)
root.right.left = TreeNode(-7)
root.right.right = TreeNode(15)

出力

[5, -10, 4, -2, -7, 15]