二叉树中和替某一值的路径（剑指offer+二叉树+递归）

二叉树中和为某一值的路径（剑指offer+二叉树+递归）

题目链接：http://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

放着很久了，从根节点出发，我每次到叶子结点就统计这条路径的和，如果正好等于所求值，那么我就把这条路径放入vector的二维数组中，否则返回他的父节点，并把值从path里删除，用pop_back();这里用vector比用stack好！最后返回他，当然我们需要特判空树；

思路就是这样，关键是书写的时候，要注意细节。

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};
class Solution {
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int> > ans;
        if(!root) return ans;
        vector<int> path;
        int cnt=0;
        FindPath(root,expectNumber,path,cnt,ans);
        return ans;

    }
    void FindPath(TreeNode* root,int expectNumber,vector<int> path,int sum,vector<vector<int> >&ans)
    {
        sum+=root->val;
        path.push_back(root->val);

        //如果是叶子结点，判断
        if(sum==expectNumber && root->left==NULL && root->right==NULL)
        {
 /*           vector<int>::iterator iter = path.begin();
            for(;iter!=path.end();iter++)
            printf("%d\t",*iter);
            printf("\n");*/
            ans.push_back(path);
        }

        //非叶子
        if(root->left)
        {
            FindPath(root->left,expectNumber,path,sum,ans);
        }
        if(root->right)
        {
            FindPath(root->right,expectNumber,path,sum,ans);
        }
        //返回父节点
        path.pop_back();
    }
};
int main()
{
    Solution so;
    TreeNode* tr;
    TreeNode *T=new TreeNode(10);
    tr=T;
    TreeNode* p=new TreeNode(5);
    tr->left=p;
    p=new TreeNode(12);
    tr->right=p;
    tr=tr->left;

    p=new TreeNode(4);
    tr->left=p;
    p=new TreeNode(7);
    tr->right=p;

    vector<vector<int> > arr=so.FindPath(T,22);
    for(int i=0;i<arr.size();i++)
    {
        vector<int>::iterator iter = arr[i].begin();
        for(;iter!=arr[i].end();iter++)
        printf("%d\t",*iter);
        printf("\n");
    }
    return 0;
}

/*
测试用例:
{10,5,12,4,7},22

对应输出应该为:
[[10,5,7],[10,12]]
*/

最近在做面试题，各种虐心啊，今天做了一下午的性格测试。明天又有笔试了！

终于体会到找工作的不容易了。没有那种纯粹的心了，不能像搞acm那样研究自己感兴趣的东西了。

希望自己可以找到一份另自己满意的工作，给我的大学画上一个完美的句点。加油！