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.
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.
需要注意的是,在这里路径的起点必须是根节点,终点必须是叶节点。如果中间某节点已经达到总和要求,也必须继续向下遍历。
# 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
如对本文有疑问, 点击进行留言回复!!
【状压dp】[HDU1400 & poj2411] Mondriaan‘s Dream
Qt + Python + OpenCV图标替换工具 之 Qt界面设计(四)
网友评论