LeetCode Q113: 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]
]

Solution

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	void helper(TreeNode* node, int sum, vector<vector<int> >& H, vector<int> path){
	path.push_back(node->val);
	if(node->left==NULL&&node->right==NULL){
	int psum=0;
	for(int i=0; i<path.size(); ++i)
	psum+=path[i];
	if(psum==sum)
	H.push_back(path);
	return;
	}
	if(node->left!=NULL)
	helper(node->left, sum, H, path);
	if(node->right!=NULL)
	helper(node->right, sum, H, path);
	return;
	}
	vector<vector<int>> pathSum(TreeNode* root, int sum) {
	vector<vector<int> > res;
	if(root==NULL)
	return res;
	vector<int> path;
	helper(root, sum, res, path);
	return res;
	}
	};

view raw Q113PathSumII.cpp hosted with ❤ by GitHub

Round2 solution:

	class Solution {
	public:
	void helper(TreeNode* root, vector<vector<int> >& res, vector<int>& curRes, int sum, int curSum){
	if(root==NULL)
	return;
	if(root->left==NULL&&root->right==NULL)
	if(sum == curSum+root->val){
	curRes.push_back(root->val);
	res.push_back(curRes);
	curRes.pop_back();
	}
	curRes.push_back(root->val);
	helper(root->left, res, curRes, sum, curSum+root->val);
	helper(root->right, res, curRes, sum, curSum+root->val);
	curRes.pop_back();
	}
	vector<vector<int>> pathSum(TreeNode* root, int sum) {
	vector<vector<int> > res;
	vector<int> curRes;
	int curSum = 0;
	helper(root, res, curRes, sum, curSum);
	return res;
	}
	};

view raw Q113Rnd2.cpp hosted with ❤ by GitHub