题解 | #二叉树中和为某一值的路径(二)#

递归，深度优先搜索+回溯。

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param target int整型 
# @return int整型二维数组
#
class Solution:
    def FindPath(self , root: TreeNode, target: int):
               
        def dfs(root: TreeNode, target: int, ans):
            # 处理树为空
            if not root: 
                return []
            # 不是空树就把值加入路径
            path.append(root.val)
            # 更新
            ans += root.val
            # 如果递归当前节点为叶子节点且该条路径的值已经达到了target，则更新res
            if not root.left and not root.right and target == ans:
                res.append(path[:])
            # 深度优先搜索加回溯
            # 左右子树递归
            dfs(root.left, target, ans)#左子树非空。遍历左子树
            dfs(root.right, target,ans)#右子树非空，遍历右子树
            path.pop()#回溯
            # 左右子树都为空，到达叶子节点，path弹出最后一个元素开始回溯。其实对于回溯不是完全理解透彻。
            
        res, path = [], []
        dfs(root, target,0)
        return res

另一个等价写法。加深理解。

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param target int整型 
# @return int整型二维数组
#
class Solution:
    def FindPath(self , root: TreeNode, target: int):
               
        def dfs(root: TreeNode, target: int):
            # 处理树为空
            if not root: 
                return
            # 不是空树就把值加入路径
            path.append(root.val)
            # 更新
            target -= root.val
            # 如果递归当前节点为叶子节点且该条路径的值已经达到了expectNumber，则更新ret
            if not root.left and not root.right and target == 0:
                ret.append(path[:])#深拷贝
            # 左右子树递归
            else:
                if root.left:
                    dfs(root.left, target)#左子树非空，先遍历右子树
                if root.right:
                    dfs(root.right, target)#右子树非空，再遍历右子树
            path.pop()#左右子树都为空，到达叶子节点，回溯
            
        ret, path = [], []
        dfs(root, target)
        return ret

如何深度优先搜索+回溯：

• 出口：if not root: return
• 递归条件：如果没有到达叶子节点，就继续往下进行递归。
• 每层递归最后要回溯。

时间复杂度：O(n)

空间复杂度：O(n)

说明： res和path用了全局变量的形式，而不能把它们写成类的属性（就像self.res,self.path，试过这样定义，代码结果不对）。

全局res=[]，可以在子函数里面用res.append()每次不会覆盖地追加元素；但是如果全局变量是一个数，比如a=0，在子函数里面用a=a+1，就会报错局部变量referenced before assignment。

【如果函数内无global关键字，优先读取局部变量，无局部变量则读取全局变量，不能对全局变量重新赋值】