Leetcode---Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

Show Tags

Have you met this question in a real interview?

这道题关键的地方在于如何传递一个vector，让它在递归中不停的存数据，递归完了之后，又能弹出之前的数据。

所以，一个关键的技巧就是不传引用，而是传值。这样，每次递归的时候，实际上都会在栈上生成一个新的参数，递归结束的时候，原传入参数没有受到任何影响。再回到上一层，就像是弹出了。

好像是在说天书，好吧，看下面两个实现，一个是用引用类型的，一个是用值类型的，都Accept了
引用类型：

vector<vector<int> > result;
void pathSumHelper(TreeNode *root, int sum, vector<int>& tmp){
    if(root==NULL)
        return;
    if(root->left==NULL &&root->right==NULL){
        if(sum==root->val){
            tmp.push_back(root->val);
            result.push_back(tmp);
        }
        return;
    }
    sum-=root->val;
    tmp.push_back(root->val);
    vector<int> tmp2(tmp);
    vector<int> tmp3(tmp);
    pathSumHelper(root->left,sum,tmp2);
    pathSumHelper(root->right,sum,tmp3);
    sum+=root->val;
    tmp.pop_back();

}
vector<vector<int> > pathSum(TreeNode *root, int sum) {
    vector<int> tmp;
    pathSumHelper(root,sum,tmp);
    return result;
}

其实就是在传入的时候copy了一把。但是注意，每个函数都要copy一把，否则又会错。

然后是值类型的：

vector<vector<int> > result;
void pathSumHelper(TreeNode *root, int sum, vector<int> tmp){
    if(root==NULL)
        return;
    if(root->left==NULL &&root->right==NULL){
        if(sum==root->val){
            tmp.push_back(root->val);
            result.push_back(tmp);
        }
        return;
    }
    sum-=root->val;
    tmp.push_back(root->val);
    pathSumHelper(root->left,sum,tmp);
    pathSumHelper(root->right,sum,tmp);
    sum+=root->val;
    tmp.pop_back();

}
vector<vector<int> > pathSum(TreeNode *root, int sum) {
    vector<int> tmp;
    pathSumHelper(root,sum,tmp);
    return result;
}

非常整齐的代码，但是因为是值传递，第17行tmp.pop_back();可以不要，因为函数结束了tmp其实也销毁了。