Python 中檢查兩棵二叉樹的葉子遍歷是否相同

假設我們有兩棵二叉樹。我們需要檢查這兩棵樹的葉子遍歷是否相同。眾所周知，葉子遍歷是從左到右遍歷葉子的序列。

因此，如果輸入如下所示：

則輸出將為 True，因為兩棵樹的左側遍歷序列相同，即 [5, 7, 8]。

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

  • s1 := 一個新的列表，s2 := 另一個新的列表
  • 將 r1 插入 s1，將 r2 插入 s2
  • 當 s1 和 s2 不為空時，執行以下操作：
    • 如果 s1 為空或 s2 為空，則
      • 返回 False
    • r1_node := s1 的最後一個節點，並將其從 s1 中刪除
    • 當 r1_node 不等於 null 且 r1_node 不是葉子節點時，執行以下操作：
      • 如果 r1_node 的右子節點不等於 null，則
        • 將 r1_node 的右子節點插入 s1 的末尾
      • 如果 r1_node 的左子節點不等於 null，則
        • 將 r1_node 的左子節點插入 s1 的末尾
        • r1_node := s1 的最後一個節點，並將其從 s1 中刪除
    • r2_node := s2 的最後一個節點，並將其從 s2 中刪除
    • 當 r2_node 不等於 null 且 r2_node 不是葉子節點時，執行以下操作：
      • 如果 r2_node 的右子節點不等於 null，則
        • 將 r2_node 的右子節點插入 s2 的末尾
      • 如果 r2_node 的左子節點不等於 null，則
        • 將 r2_node 的左子節點插入 s2 的末尾
      • r2_node := s2 的最後一個節點，並將其從 s2 中刪除
    • 如果 r1_node 為 null 且 r2_node 不為 null，則
      • 返回 False
    • 如果 r1_node 不為 null 且 r2_node 為 null，則
      • 返回 False
    • 如果 r1_node 和 r2_node 均不為 null，則
      • 如果 r1_node 的值不等於 r2_node 的值，則
        • 返回 False
  • 返回 True

示例

讓我們看一下以下實現，以便更好地理解：

 線上演示

class TreeNode:
   def __init__(self, x):
      self.val = x
      self.left = self.right = None
   def is_leaf(self):
      return self.left == None and self.right == None
def solve(r1, r2):
   s1 = []
   s2 = []
   s1.append(r1)
   s2.append(r2)
   while len(s1) != 0 or len(s2) != 0:
      if len(s1) == 0 or len(s2) == 0:
         return False
      r1_node = s1.pop(-1)
      while r1_node != None and not r1_node.is_leaf():
         if r1_node.right != None:
            s1.append(r1_node.right)
         if r1_node.left != None:
            s1.append(r1_node.left)
            r1_node = s1.pop(-1)
      r2_node = s2.pop(-1)
      while r2_node != None and not r2_node.is_leaf():
         if r2_node.right != None:
            s2.append(r2_node.right)
         if r2_node.left != None:
            s2.append(r2_node.left)
         r2_node = s2.pop(-1)
      if r1_node == None and r2_node != None:
         return False
      if r1_node != None and r2_node == None:
   return False
if r1_node != None and r2_node != None:
if r1_node.val != r2_node.val:
return False
return True
root1 = TreeNode(2)
root1.left = TreeNode(3)
root1.right = TreeNode(4)
root1.left.left = TreeNode(5)
root1.right.left = TreeNode(7)
root1.right.right = TreeNode(8)
root2 = TreeNode(1)
root2.left = TreeNode(6)
root2.right = TreeNode(9)
root2.left.right = TreeNode(5)
root2.right.left = TreeNode(7)
root2.right.right = TreeNode(8)
print(solve(root1, root2))

輸入

root1 = TreeNode(2)
root1.left = TreeNode(3)
root1.right = TreeNode(4)
root1.left.left = TreeNode(5)
root1.right.left = TreeNode(7)
root1.right.right = TreeNode(8)
root2 = TreeNode(1)
root2.left = TreeNode(6)
root2.right = TreeNode(9)
root2.left.right = TreeNode(5)
root2.right.left = TreeNode(7)
root2.right.right = TreeNode(8)

輸出

True

更新於: 2021年1月19日

115 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告

© . All rights reserved.