leetcode 113 路径总和2

通过回溯深搜，因为题目要求的是路径，所以当节点的值满足目标值以及没有左右子节点（为叶子节点）返回，每次将当前遍历的节点放入path数组，同时目标进行作差。

同样需要注意path数组的浅复制path[:],否则result中的结果为空，因为会随着递归后path数组为空而变化。

python数组可以使用pop。
因为有负数，所以不要加大于target的剪枝操作。
注意在当前节点值等于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 pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        def dfs(r,target,path):
            if not root:
                return []
            path.append(r.val)

            if r.val==target and not r.left and not r.right:              
                result.append(path[:])
                path.pop()
                return 

            if r.left:
                dfs(r.left,target-r.val,path)
            if r.right:
                dfs(r.right,target-r.val,path)

            path.pop()


        result=[]
        path=[]

        dfs(root,targetSum,path)
        return result

广度优先遍历

# 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 pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        result=[]
        patu=[]
        queue=collections.deque()
        queue.append((root,[],0))

        #target=collections.deque([0])
        if not root:
            return []
        while queue:
            r,path,t=queue.popleft()


            if not r.left and not r.right:
                if t+r.val==targetSum:
                    result.append(path+[r.val])
                    #path.pop()
            else:
                if r.left:
                    queue.append((r.left,path+[r.val],t+r.val))
                    #target.append(t)
                if r.right:
                    queue.append((r.right,path+[r.val],t+r.val))
                    #target.append(t)
        return result

使用栈进行dfs

# 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 pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        result=[]
        queue=[]
        queue.append((root,[],0))

        #target=collections.deque([0])
        if not root:
            return []
        while queue:
            r,path,t=queue.pop()


            if not r.left and not r.right:
                if t+r.val==targetSum:
                    result.append(path+[r.val])
                    #path.pop()
            else:
                if r.right:
                    queue.append((r.right,path+[r.val],t+r.val))
                if r.left:
                    queue.append((r.left,path+[r.val],t+r.val))
                    #target.append(t)

                    #target.append(t)
        return result