• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

112. Path Sum(路径求和)

leetcode admin 3个月前 (03-30) 205次浏览 0个评论 扫描二维码

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

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

举例:

给定如下二叉树以及 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)

Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明112. Path Sum(路径求和)
喜欢 (0)
admin
关于作者:

您必须 登录 才能发表评论!