Python程式：檢查兩棵樹的結構和值是否完全相同

假設我們有兩棵二叉樹，我們需要檢查它們在結構和值方面是否完全相同。我們可以稱它們為孿生樹。

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

則第一對的輸出將為 True，第二對和第三對的輸出將為 False，因為第二對的某些值不同，而第三對的結構不同。

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

  • 定義一個名為 solve() 的方法，該方法將接收兩個根節點。

  • 如果 root0 為空且 root1 為空，則

    • 返回 True

  • 如果 root0 為空或 root1 為空，則

    • 返回 False

  • 如果 root0 的值與 root1 的值不同，則

    • 返回 False

  • 當 solve(root0 的左子樹, root1 的左子樹) 和 solve(root0 的右子樹, root1 的右子樹) 都為真時返回真，否則返回假。

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

示例

 線上演示

class TreeNode:
   def __init__(self, val, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right
class Solution:
   def solve(self, root0, root1):
      if not root0 and not root1:
         return True
      if not root0 or not root1:
         return False
      if root0.val != root1.val:
         return False
      return self.solve(root0.left, root1.left) and
self.solve(root0.right, root1.right)
ob = Solution()
root1 = TreeNode(10)
root1.left = TreeNode(5)
root1.right = TreeNode(15)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(8)
root2 = TreeNode(10)
root2.left = TreeNode(5)
root2.right = TreeNode(15)
root2.left.left = TreeNode(3)
root2.left.right = TreeNode(8)
print(ob.solve(root1, root2))

輸入

root1 = TreeNode(10) root1.left = TreeNode(5) root1.right =
TreeNode(15) root1.left.left = TreeNode(3) root1.left.right =
TreeNode(8) root2 = TreeNode(10) root2.left = TreeNode(5)
root2.right = TreeNode(15) root2.left.left = TreeNode(3)
root2.left.right = TreeNode(8)

輸出

True

更新於: 2020年10月21日

101 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告