题目描述

输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

思路

（1）用先序遍历树，访问某一个节点的时候，先把这个节点加到路径中去，并把这个节点的值进行累加。
（2）如果这个节点是叶子节点，那就进行比较，如果等于指定值，那就把这整条路径加道全部路径中；如果不等于，那就返回到根节点去(注意要把当前路径中的它去掉，还要把累计值中的减掉)
（3）如果不是叶子节点，就继续遍历它的左子树和右子树（注意：在返回到根节点的时候同样需要把自己去掉）

这里还有的需要注意的就是：
对于当前路径和全部路径都需要一直进行保存，所以需要用引用传递；另外累计和用不用引用传递都可以(具体区别代码中有注释)

代码

class Solution {
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int>> allPath;
        vector<int> currentPath;
        int currentSum=0;
        if(root==NULL)
            return allPath;  //这个一定别忘了啊，关于树的题目一定要考虑为空
        SinglePath(root,expectNumber,allPath,currentPath,currentSum);
        return allPath;
    }

    void SinglePath(TreeNode* root,int expectNumber,vector<vector<int>> &allPath,vector<int> &currentPath,int currentSum)
    {
        currentSum+=root->val;       //每次遍历到一棵树，先把它加到当前路径中去
        currentPath.push_back(root->val);

        //如果是叶子节点，并且路径上节点值的和等于指定值，就把这条路径加到全部路径中去
        bool isLeaf=root->left==NULL&&root->right==NULL;
        if(currentSum==expectNumber&&isLeaf)
        {
            allPath.push_back(currentPath);
        }
        //如果有左子树，就继续遍历左子树
        if(root->left!=NULL)
        {
            SinglePath(root->left,expectNumber,allPath,currentPath,currentSum);
        }
        //如果有右子树，就继续遍历右子树
        if(root->right!=NULL)
        {
            SinglePath(root->right,expectNumber,allPath,currentPath,currentSum);
        }
        //在返回父节点之前，在路径在删除当前节点
        currentPath.pop_back();
        //下面这句话需不需要就要看这个函数中的currentSum是值传递还是引用传递，如果是引用传递就需要加(因为在递归内部把子节点加进去了)
        //currentSum-=root->val;
        //如果是值传递就不需要加（因为递归内部改变它不影响外部根节点的）
    }
};