LeetCode112.Path Sum
LeetCode113.Path Sum II
LeetCode437.Path Sum III
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
需要注意的是,在这里路径的起点必须是根节点,终点必须是叶节点。如果中间某节点已经达到总和要求,也必须继续向下遍历。
Code
Recursive
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if root:
sum -= root.val
if sum == 0 and self.isLeaf(root):
return True
else:
return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)
def isLeaf(self, root):
if root:
if root.left is None and root.right is None:
return True
return False
一个错误的思想是在达到sum值后直接通过判断是否为叶节点就进行返回,这样的话就是属于我们前面说的终点不一定是叶节点的情况,也有可能是中间节点已经满足sum值,这时候直接返回其是否为叶节点,如果不是则直接被判为False,这就忽略了在其之后的节点和为0的情况。
if sum == 0 :
return self.isLeaf(root)
else:
return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)
在这里要区别局部函数和全局类函数,一个需要在调用时候加self.function一个不需要;
另外需要区别开node和root,sum和target
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root:
return False
def update(node, target):
if not node:
return False
target -= node.val
if target == 0 and self.isLeaf(node):
return True
else:
return update(node.left, target) or update(node.right, target)
return update(root, sum)
def isLeaf(self, root):
if root:
if root.left is None and root.right is None:
return True
return False
本文地址:https://blog.csdn.net/qq_41704019/article/details/107449738
上一篇: python中字典的增删改查
下一篇: python开发入门——环境搭建
推荐阅读
-
sum(case when then)(判断男女生的个数)
-
sql中count或sum为条件的查询示例(sql查询count)
-
linux比较两个文件是否一样(linux命令md5sum使用方法)
-
mysql踩坑之limit与sum函数混合使用问题详解
-
Python中使用md5sum检查目录中相同文件代码分享
-
[codewars_python]Sum of Digits / Digital Root
-
基于Python中求和函数sum的用法详解
-
对python中array.sum(axis=?)的用法介绍
-
python 列表,数组和矩阵sum的用法及区别介绍
-
sum(case when then)(判断男女生的个数)