112. Path Sum(路径求和)

1,395次阅读
没有评论

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

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

举例:

给定如下二叉树以及 sum = 22,

      <strong>5</strong>
     <strong>/</strong> \
    <strong>4</strong>   8
   <strong>/</strong>   / \
  <strong>11</strong>  13  4
 /  <strong>\</strong>      \
7    <strong>2</strong>      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)
admin
版权声明:本站原创文章,由admin2019-03-30发表,共计864字。
转载提示:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)