题目：二叉树根节点到叶子节点和为指定值的路径

描述：给定一个二叉树和一个值 sum，请找出所有的根节点到叶子节点的节点值之和等于 sum的路径，例如：给出如下的二叉树， sum=22，图如下所示：

返回[[5,4,11,2],[5,8,9]]。

解法一：

思路分析：首先，通读题目，通过理解相应题目，我们可以采用递归的方法去解决问题，如果递归的当前结点不是叶子结点，就把sum减去当前的值，并把当前结点当作路径添加到临时的数组当中去，然后去检查其左右结点，如果是叶子结点的话，检查其剩余的sum值是否与该值相等，如果相等就把最终结果放到最后的res容器当中去。

实例分析：输入为[5，4，8，1，11，#，9，#，#，2，7]，Sum = 22。

首先定义一个res的容器，作为最终存放的结果。

存放的数值

5

target = 22 - 5 = 17

遍历5的左子树

4

target = 17 - 4 = 13

遍历4的左子树

1

target = 13 - 1 = 12

因为已经到了叶子结点，计算的值不等于最终值，故返回上一层

遍历4的右子树

11

target = 13 - 11 = 2

遍历11的左子树

2

target = 2 - 2 = 0

将这次的计算结果返回到res容器当中，返回上一层

遍历11的右子树

7

target = 2 - 7（不符合条件）

返回上一层的上一层

遍历5的右子树

8

target = 17 - 8 = 9

遍历8的右子树

9

target = 9 - 9 = 0

将最终结果存放到res容器当中，结束运算

具体C++代码如下所示： 


/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */
 
class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return int整型vector<>>
     */
    vector res;
    vector pathSum(TreeNode* root, int sum) {
        // write code here
        vector path;
        run(sum, root, path);//定义一个run函数
        return res;
    }
    
    void run(int target,TreeNode* node,vectorpath){
        if(node == nullptr)//如果未空，则不进行计算
            return ;
        path.push_back(node->val);//将根节点的值添加到容器当中
        if(node->left == nullptr && node->right == nullptr){//如果没有左右节点
            if(target == node->val)//进行目标值的判断
                res.push_back(path);
        }
        else{
            target -= node->val;//逐层递减，进行判断
            run(target, node->left, path);
            run(target, node->right, path);
        }
    }
};


因为如果有n个数据的话，就等执行n次才能得到最终结果，所以时间复杂度为O(N)，空间复杂度为O(N)。

具体python代码如下所示： 
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
 
#
#
# @param root TreeNode类
# @param sum int整型
# @return int整型二维数组
#
class Solution:
    def pathSum(self , root , sum ):
        # write code here
        res = []
        self.dfs(root, sum, [], res)#调用该函数
        return res#返回该数组
    
    def dfs(self, root, sum, temp, res):
        if not root:#特殊情况
            return
        if not root.left and not root.right and sum == root.val:
            res.append(temp + [root.val])#将该值加入到数组当中去
            return
        temp.append(root.val)#扩展进去
        self.dfs(root.left, sum - root.val, temp, res)#递归执行
        self.dfs(root.right, sum - root.val, temp, res)
        temp.pop()
时间复杂度为O(N)，空间复杂度为O(N)。

解法二：

        思路分析：同样，我们可以采用迭代法进行计算，首先按照先序遍历的特点，遍历树中的所有结点，在先序遍历中，要记录路径值，只要等于目标值的话，就将路径加入到最终的列表当中。

        具体python代码为： 
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
# 
# @param root TreeNode类 
# @param sum int整型 
# @return int整型二维数组
#
class Solution:
    def pathSum(self , root , sum ):
        # write code here
        ress = []#用于存储最终结果
        lujing = []
        def repath(root, goil):
            if not root: return
            lujing.append(root.val)##将根节点的值添加
            goil -= root.val
            if goil == 0 and not root.left and not root.right:#判断条件为该值是否为0或者左右子树是否为空
                ress.append(list(lujing))#返回到最终的res容器中
            repath(root.left, goil)#遍历左子树
            repath(root.right, goil)#遍历右子树
            lujing.pop()
        repath(root, sum)
        return ress
因为采用先序遍历遍历树中全部的元素，所以其时间复杂度为O(N)，需要额外的内存空间res和lujing，所以其时间复杂度为O(N)。