剑指 二叉树路径

本题可以通过递归和非递归的方法去解决，需要先理解遍历二叉树所有路径的解法，然后增加路径和约束即可。递归方法也有两种，一个是维护全局变量数组，需要每次在最后进行回溯，第二个是传递参数，这样就不用回溯。非递归的方法就是通过队列帮助,注意在队列中传入节点，以及节点之前的路径。

通过递归函数，每次记录下经过的值，然后分别去访问其子树节点，最后回溯。注意需要回溯，因为不管判断节点是否在结果路径中，判断完都应该去除该节点。

class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def __init__(self):
        self.path=[]
        self.allpath=[]
    def dfs(self,root,sumval):
        self.path.append(root.val)
        if not root.left and not root.right:
            if root.val==sumval:
                self.allpath.append(self.path)
                #self.path=self.path[:-1]


        if root.left:
            self.dfs(root.left,sumval-root.val)
        if root.right:
            self.dfs(root.right,sumval-root.val)
        self.path=self.path[:-1]


    def FindPath(self, root, expectNumber):
        # write code here
        if root==None:
            return []
        self.dfs(root,expectNumber)
        return self.allpath

遍历所有路径 递归方法 同样注意回溯。

class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def __init__(self):
        self.path=[]
        self.allpath=[]
    def dfs(self,root):
        self.path.append(root.val)
        if not root.left and not root.right:

            self.allpath.append(self.path)
                #self.path=self.path[:-1]

        if root.left:
            self.dfs(root.left)
        if root.right:
            self.dfs(root.right)
        self.path=self.path[:-1]   

    def FindPath(self, root, expectNumber):
        # write code here
        if root==None:
            return []
        self.dfs(root)
        return self.allpath

通过传递参数的方法，来实现回溯功能。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def __init__(self):
        self.path=[]
        self.allpath=[]
    def dfs(self,root,path):
        #self.path.append(root.val)
        if not root.left and not root.right:

            self.allpath.append(path)
                #self.path=self.path[:-1]


        if root.left:
            self.dfs(root.left,path+[root.left.val])
        if root.right:
            self.dfs(root.right,path+[root.right.val])
        #self.path=self.path[:-1]


    def FindPath(self, root, expectNumber):
        # write code here
        if root==None:
            return []
        path=[root.val]
        self.dfs(root,path)
        return self.allpath

非递归方法，借助队列，在python2中使用collections.deque 会有问题。
collections.deque[()],将路径也存储进去，这样层序遍历的时候，queue 同时也会存储当前节点之前的路径。

class Solution:
    def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
        if root==None:
            return []
        queue=collections.deque([(root,[root.val])])
        #queue.append(root)

        visit=[]

        result=[]
        while queue:
            item,path=queue.popleft()

            if item.left==None and  item.right==None:
                result.append(path)
            if item.left:
                queue.append((item.left,path+[item.left.val]))
            if item.right:
                queue.append((item.right,path+[item.right.val]))


        return result

非递归方法来找路径之和为目标值的路径。借用队列

class Solution:
    def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
        if root==None:
            return []
        queue=collections.deque([(root,[root.val],target)])
        #queue.append(root)



        result=[]
        while queue:
            item,path,sumval=queue.popleft()

            if item.left==None and item.right==None and sumval==item.val:
                result.append(path)
            if item.left:
                queue.append((item.left,path+[item.left.val],sumval-item.val))
            if item.right:
                queue.append((item.right,path+[item.right.val],sumval-item.val))


        return result