112. 路径总和,113. 路径总和 II,437. 路径总和 III
程序员文章站
2022-05-20 12:21:01
...
112. 路径总和-是否存在路径和=target
思路1:改自113题
class Solution:
def hasPathSum(self, root: TreeNode, sumv: int) -> bool:
ans,path = [],[]
def helper(node):
if not node: return
path.append(node.val)
if not node.left and not node.right:
if sum(path)==sumv: ans.append(1)
helper(node.left)
helper(node.right)
path.pop(-1)
helper(root)
return True if ans else False
简单版本:
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root: return False
if (not root.left and not root.right)and root.val==sum:return True
return self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val)
思路3:前序非递归
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
# 前序非递归
if not root:return False
stack=[(root,sum)]
while stack:
node,sumval = stack.pop()
if (not node.left) and (not node.right)and (node.val== sumval):return True
if node.right:stack.append((node.right,sumval-node.val))
if node.left:stack.append((node.left,sumval-node.val))
sum+=node.val
return False
113. 路径总和 II-路径和=target给出路径
思路1:回溯法。
深度递归遍历,当遇到叶子节点的时候判断路径和,退出时回溯,去掉路径的值。
注意:ans.append(path[:]一定要复制而非应用,倒腾了半天,又忘了这个。
时间复杂度:O(n)
空间复杂度:O(n)
class Solution:
def pathSum(self, root: TreeNode, sumv: int) -> List[List[int]]:
ans,path = [],[]
def helper(node):
if not node: return
path.append(node.val)
if not node.left and not node.right:
if sum(path)==sumv: ans.append(path[:]) # 注意
helper(node.left)
helper(node.right)
path.pop(-1)
helper(root)
return ans
437. 路径总和 III-路径总数(包括子路径)
给定一个二叉树,它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
参考解答:简单易懂方法
思路1:基于113题,检查每条路径的符合条件的子路径,这个时间复杂度快到O(n3),肯定超时。
思路2:把每个节点看做根节点,执行求路径总数的操作。时间复杂度为O(n2)
相当于递归里面嵌套一个递归。
class Solution:
def pathSum(self, root: TreeNode, sumv: int) -> int:
# 对于每个节点,都计算符合sum的路径数目
if not root:return 0
s= self.count(root,sumv)
return s+self.pathSum(root.left,sumv)+self.pathSum(root.right,sumv)
def count(self,node,sumval):
# 计算以当前节点为根,符合目标值的路径数目
if not node:return 0
s=1 if node.val == sumval else 0
newsum = sumval-node.val
return s+self.count(node.left,newsum)+self.count(node.right,newsum)
思路3:
需要完全掌握
如何通过一次遍历实现?
->需要访问到一个节点的时候可以判断其子路径符合条件的数目
->sum(abc)-sum(ab)=target=>sum(bc)=target 从而可以判断出非根节点出发的子路径和
->从而不断移动终点,就可以确定不同起点和终点的子路径和
class Solution(object):
def pathSum(self, root, sum):
def helper(node,target,pathsum,sumdic):
if not node:return 0
result = 0 # 当前节点为终点的路径存在的所有符合数目
pathsum+=node.val # 新的以根节点为起点的路径和
if pathsum==target: result+=1 # 符合 路径数+1
result += sumdic.get(pathsum-target,0) # 符合的以非根节点为起点的路径和数目
sumdic[pathsum] = sumdic.get(pathsum,0)+1 # 增加路径和对应的数目
result += helper(node.left,target,pathsum,sumdic)
result += helper(node.right,target,pathsum,sumdic)
sumdic[pathsum]-=1 # 减少路径和对应的数目
return result
return helper(root,sum,0,{})
上一篇: C#的virtual方法小结