Python 程式檢查樹的中序遍歷序列是否為迴文

假設我們有一棵二叉樹，其中每個節點包含一個 0-9 的數字，我們需要檢查其中序遍歷是否為迴文。

因此，如果輸入類似於

則輸出將為 True，因為其中序遍歷為 [2,6,10,6,2]。

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

  • 如果根節點為空，則
    • 返回 True
  • stack := 新棧
  • curr := 根節點
  • inorder := 新列表
  • 當棧不為空或 curr 不為空時，執行以下操作
    • 當 curr 不為空時，執行以下操作
      • 將 curr 推入棧
      • curr := curr 的左節點
    • node := 從棧中彈出的元素
    • 將 node 的值插入 inorder 列表末尾
    • curr := node 的右節點
  • 當 inorder 與 inorder 的逆序相同則返回 true，否則返回 false。

讓我們看看以下實現以獲得更好的理解 -

示例

 線上演示

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 True
      stack = []
      curr = root
      inorder = []
      while stack or curr:
         while curr:
            stack.append(curr)
            curr = curr.left
         node = stack.pop() inorder.append(node.val)
         curr = node.right
      return inorder == inorder[::-1]
ob = Solution()
root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(2)
print(ob.solve(root))

輸入

root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(2)

輸出

True

更新於: 2020年10月20日

197 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告