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

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

　　树结构的定义如下：

1 struct TreeNode {
2     int val;
3     struct TreeNode *left;
4     struct TreeNode *right;
5     TreeNode(int x) :
6             val(x), left(NULL), right(NULL) {
7     }
8 };

　　解析：由于路径是从根节点出发到叶节点，也就是说路径总是以根节点为起始点，因此我们需要遍历根节点。在二叉树的前序、中序、后序遍历中，只有前序遍历是首先访问根节点的。本题的算法中主要有以下几步：

　　1、前序遍历访问到某个节点时，将该节点添加到路径上，并累加该节点的值；

　　2、如果该节点为叶节点，并且路径中的节点值的和刚好等于输出的整数，则当前路径符合要求；

　　3、如果当前节点不是叶节点，则继续访问它的子节点；

　　4、递归结束之后，将自动回到它的父节点，因此要在退出之前在路径中删除掉当前节点。

　　根据这几点，便可以前序遍历为基础写出改代码：

 1 vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
 2     vector<vector<int>> findPath;
 3     vector<int> path;
 4     int currentSum = 0;
 5     if(root == NULL)
 6         return findPath;
 7     FindPath(root,expectNumber,path,findPath,currentSum);
 8     return findPath;
 9 }
10 
11 void FindPath(TreeNode* root,int expectNumber,vector<int>& path,vector<vector<int>>& findPath,int currentSum){
12     //前序遍历访问到某个节点时，将该节点添加到路径上，并累加该节点的值；
13     currentSum+=root->val;
14     path.push_back(root->val);
15     bool isLeaf = root->left==NULL && root->right==NULL;
16     //如果该节点为叶节点，并且路径中的节点值的和刚好等于输出的整数，则当前路径符合要求；
17     if(isLeaf && currentSum == expectNumber){
18         findPath.push_back(path);
19     }
20     //如果当前节点不是叶节点，则继续访问它的子节点；
21     if(root->left!=NULL)
22         FindPath(root->left,expectNumber,path,findPath,currentSum);
23     if(root->right!=NULL)
24         FindPath(root->right,expectNumber,path,findPath,currentSum);
25     //递归结束之后，将自动回到它的父节点，因此要在退出之前在路径中删除掉当前节点。
26     path.pop_back();
27 }