Python程式檢查二叉樹中每個節點（除葉子節點外）的值是否等於其子節點值之和

假設我們有一個二叉樹，我們需要檢查樹中每個節點（除葉子節點外）的值是否等於其左子節點和右子節點的值之和。

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

則輸出為 True

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

• 定義一個函式 dfs()。它將接收根節點作為引數。

• 如果根節點為空，則

  • 返回 True

• 如果根節點的左子節點和右子節點都為空，則

  • 返回 True

• left := 0

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

  • left := 根節點左子節點的值

• right := 0

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

  • right := 根節點右子節點的值

• 當 (left + right 等於根節點的值) 並且 dfs(根節點的左子節點) 為真 並且 dfs(根節點的右子節點) 為真時，返回 true

• 在主方法中執行以下操作：

• 返回 dfs(根節點)

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

示例

 線上演示

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):
      def dfs(root):
         if root == None:
            return True
         if root.left == None and root.right == None:
            return True
         left = 0
         if root.left:
            left = root.left.val
         right = 0
         if root.right:
            right = root.right.val
         return (left + right == root.val) and dfs(root.left) and
      dfs(root.right)
return dfs(root)
ob = Solution()
root = TreeNode(18)
root.left = TreeNode(8)
root.right = TreeNode(10)
root.left.left = TreeNode(3)
root.left.right = TreeNode(5)
print(ob.solve(root))

輸入

root = TreeNode(18) root.left = TreeNode(8) root.right = TreeNode(10)
root.left.left = TreeNode(3) root.left.right = TreeNode(5)

輸出

True

Arnab Chakraborty

更新於: 2020年10月21日

265 次瀏覽

啟動您的 職業生涯

透過完成課程獲得認證

開始學習