过邮件遍历以计算二叉树中的路径总和

Question

我正在努力解决问题Path Sum - LeetCode。

112. 路径总和

给定二叉树和求和，确定树是否具有根到叶路径，使得沿路径的所有值相加等于给定的总和。

注意：叶子是没有子节点的节点。

例：

鉴于以下二叉树和sum = 22，

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

返回true，因为存在一个根到叶的路径5->4->11->2，其总和为22。

我计划通过直观的下订单遍历来解决它。

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:

    def postorder(self, root):
        if not root: return 
        self.postorder(root.left)
        self.postorder(root.right)
        loc_sum = loc_sum + self.postorder(root.val)

然后我不知道我怎么能继续下去。你能提一些提示吗？

Answer 1

正如@meowgoesthedog指出的那样，你可以使用递归来解决这个问题。在下面的示例中，我沿着树向下，同时使用当前值减少所需的总和。只要有一个左或右节点（如果两者都存在，它会检查它们），我一直这样做。如果没有找到左边和没有右边的元素（这意味着你击中了一片叶子）我只是检查剩余的所需总和是否等于当前值。您只需使用hasPathSum(,root,sum):函数即可完成此操作，但也可以使用单独的postOrder函数。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if root.left: 
           if return self.hasPathSum(root.left, sum-root.val): return True
        if root.right:
           if return self.hasPathSum(root.right, sum-root.val): return True
        else: return root.val == sum