二叉树路径和的深度解析与算法优化

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""


class Solution:
    """
    @param: root: the root of binary tree
    @param: target: An integer
    @return: all valid paths
    """
    def binaryTreePathSum(self, root, target):
        # write your code here
        
        results = []
        self.dfs(root, results, [], 0, target)
        
        return results 
    
    def dfs(self, root, results, path, sums, target):
        if not root: return
        
        path.append(root.val)
        sums += root.val
        
        #如果要加return的话，需要pop掉一个值，否则path的值除了第一个，后面都是大于target的
        if not root.left and not root.right and sums == target:
            results.append(path[:])
            path.pop()
            return 
            
        self.dfs(root.left, results, path, sums, target)
        self.dfs(root.right, results, path, sums, target)
        #回溯，往回删除,找根节点
        path.pop()