Python實現交替層序遍歷二叉樹的程式

假設我們有一個二叉樹，我們需要交替地從左到右、從右到左顯示每一層的節點值。

例如，輸入：

則輸出為：[5, -10, 4, -2, -7, 15]

為了解決這個問題，我們將遵循以下步驟：

  • 如果根節點為空，則

    • 返回一個新的列表

  • s1 := 初始包含根節點的列表

  • s2 := 一個新的列表

  • res := 一個新的列表

  • 當s1或s2不為空時，執行以下操作：

    • 當s1不為空時，執行以下操作：

      • node := 從s1刪除最後一個元素

      • 如果node的左子節點不為空，則

        • 將node的左子節點新增到s2的末尾

      • 如果node的右子節點不為空，則

        • 將node的右子節點新增到s2的末尾

      • 將node的值新增到res的末尾

    • 當s2不為空時，執行以下操作：

      • node := 從s2刪除最後一個元素

      • 如果node的右子節點不為空，則

        • 將node的右子節點新增到s1的末尾

      • 如果node的左子節點不為空，則

        • 將node的左子節點新增到s1的末尾

      • 將node的值新增到res的末尾

  • 返回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]

更新於：2020年10月10日

101 次檢視

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告