Sunday, October 5, 2014

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]
]


class Solution {
public:
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        vector<vector<int>> ret;
        vector<int> vr;
        helper(root, sum, vr, ret);
       
        return ret;
    }
   
    void helper(TreeNode *root, int sum,vector<int> &vr, vector<vector<int>> &r)
    {
        if (root==NULL)
        return;
        vr.push_back(root->val);
        if (root->val==sum && root->left==NULL && root->right==NULL)
        {
            r.push_back(vr);
        }
       
        helper(root->left, sum-root->val, vr, r);
        helper(root->right, sum-root->val, vr, r);
        vr.pop_back(); //Be very careful about this ,otherwise, there will be TLE
    }
};

No comments:

Post a Comment