112. Path Sum(路径求和)

3,044次阅读

共计 864 个字符，预计需要花费 3 分钟才能阅读完成。

给定一个二叉树和一个和，确定该树是否有一个根到叶的路径，以便将路径上的所有值相加等于给定的和。

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

举例:

给定如下二叉树以及 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 get_sum(node,val):
            if node :
                #获取自顶向下经过的节点值累计求和
                val=val+node.val
                #判断有效的路径的条件，左右节点为空即叶子节点，值相等
                if val==sum and not node.left and not node.right:
                    return True
                #递归求解，左右子树都要递归查找，只要其中一个返回即可，所以使用或条件
                return get_sum(node.left,val) or get_sum(node.right,val)
            
            return False
            
            
        flag=get_sum(root,0)
        return flag

从discuss区域找到一个代码脚本类似思路类似，不过写的更简洁一点

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right:
            return root.val == sum
        return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)

正文完

请博主喝杯咖啡吧！