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

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

【思路】如果我们用语言表述的话，从头节点开始，走向叶节点，每条路都走一遍，然后判断每个路径的和是不是expectNumber,这就是DFS的思想。由于我们需要记录住每条路径，因此我们必须在每次递归后将trace的状态恢复为原来的状态，这样才可以达到共享trace空间的作用！

递归结束后将trace空间恢复到原来状态，这一操作也叫做回溯法！！！

/*
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) {
      if(root==NULL){
         return res;
      }
      preorder(root,expectNumber);
         return res;
      }
  void preorder(TreeNode *root,int expectNumber) {
         path.push_back(root->val);
         if(!root->left&&!root->right){
            int sum=0;
            for(int i=0;i<path.size();i++){
                sum+=path[i];
            }
         if(sum==expectNumber){
            res.push_back(path);
         }
        }
        if(root->left)
           preorder(root->left,expectNumber);
        if(root->right)
           preorder(root->right,expectNumber);
        path.erase(path.end()-1);

  }
   vector<vector<int> > res;
   vector<int> path;
};