025. 二叉树中和为某一值的路径

　　题意描述：输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

Solutions

　　首先，我们肯定要遍历这棵树，所以最好的方式递归。而当要求要判断路径的时候，知道用栈来存储，但是不能将其作为FindPathCore函数外部的一个变量，而是应该将其作为递归时的一个参数，这样才能对应到遍历时的路径上，如果是一个全局的存储，执行起来会比较乱。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.res = []
        self.expectNumber = -1
    def FindPathCore(self, root, path_s, cur_val):
        cur_val += root.val
        path_s.append(root)
        if root.left:
            self.FindPathCore(root.left, path_s, cur_val)
        if root.right:
            self.FindPathCore(root.right, path_s, cur_val)
        if not root.left and not root.right:
            if cur_val == self.expectNumber:
                path_v = []
                for item in path_s:
                    path_v.append(item.val)
                self.res.append(path_v)
        path_s.pop()
        
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        if root is None:
            return []
        self.expectNumber = expectNumber
        self.FindPathCore(root, [], 0)
        
        return self.res

Solutions

References