面试题34：二叉树中和为某一值的路径

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

思路：
这道题的思路为当访问到某一个节点，首先把该节点加入到路径中，然后再将和加上该节点的值，然后判断该节点是否为叶子节点，如果是叶子节点而且和值尾期望值，则打印，如果不是叶子节点，继续递归左节点和右节点，当递归调用返回父节点时，要删除当前节点。具体如下：

34 二叉树和为某一值的路径.png

代码实现：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        if root ==None:
            return []
        result = [] #初始化结果
        current = 0
        path = []


        def FindPathCore(root,current,path,expectNumber):
            path.append(root) #将节点加入到path
            current+=root.val

            IsLeaf = root.left == None and root.right==None

            #如果到达叶子节点
            if IsLeaf and current == expectNumber:
                pathVal = []   #将其值取出
                for node in path:
                    pathVal.append(node.val)
                result.append(pathVal)

            #如果没有到大叶子节点
            if root.left:
                FindPathCore(root.left,current,path,expectNumber)

            if root.right:
                FindPathCore(root.right,current,path,expectNumber)

            #每次要返回父节点时，需要pop出当前节点
            #因为current在每个递归调用中都是一个临时变量，
            #相当于传值引用，所以不需要对current进行减法
            path.pop()

        FindPathCore(root,current,path,expectNumber)
        return result

提交结果：