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

更新于: 2020年10月21日

265 次浏览

启动您的 职业生涯

通过完成课程获得认证

开始学习
广告