剑指 Offer 34. 二叉树中和为某一值的路径

剑指 Offer 34. 二叉树中和为某一值的路径https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/

一看就是，dfs搜到底，

走到叶子节点后看这条路径的和是否为target。

那怎么判断何为多少呢？可以把target当作一个递归参数，这样就可以看和为多少？

那怎么记录路径呢？

节点A去往下搜时，就把这个节点A加入路径中，如果节点A，后面所有路径都不满足，就把这个节点弹出去，如果节点A后面有路径满足，将path加入到结果列表中，节点A弹出去，因为，节点A已经看完了

dfs(root, tar) 函数：

递推参数： 当前节点 root ，当前目标值 tar 。
终止条件： 若节点 root 为空，则直接返回。
递推工作：
路径更新： 将当前节点值 root.val 加入路径 path ；
目标值更新： tar = tar - root.val（即目标值 tar 从 sum 减至 0 ）；
路径记录： 当 ① root 为叶节点 且 ② 路径和等于目标值 ，则将此路径 path 加入 res 。
先序遍历： 递归左 / 右子节点。
路径恢复： 向上回溯前，需要将当前节点从路径 path 中删除，即执行 path.pop() 。

 

值得注意的是，记录路径时若直接执行 res.append(path) ，则是将 path 对象加入了 res ；后续 path 改变时， res 中的 path 对象也会随之改变。

正确做法：res.append(list(path)) ，相当于复制了一个 path 并加入到 res 。

不明白的可以参考python中的引用_愈努力俞幸运的博客-CSDN博客_python 引用

运行个小例子

lst=[1,2,3,4,5]
lst1=list(lst)
lst.pop()
print(lst,lst1)

 

 

class Solution:
    def pathSum(self, root, target):
        res,path=[],[]
        def dfs(node,tar):
            if not node:return
            path.append(node.val)
            tar-=node.val
            if not node.left and not node.right and tar==0:
                res.append(list(path))
            dfs(node.left,tar)
            dfs(node.right,tar)
            path.pop()
        dfs(root,target)
        return res