Leetcode: Path Sum I&&II

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,

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

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Solve the two problems with bug free.

1. For path sum II, use the feature of C++, pass both by value and reference.
2. Vector::push_back()actually creates a copy of the argument and stores it in the vector

	Path Sum I
	bool hasPathSum(TreeNode *root, int sum) {
	return hasPathSumRe(root, 0, sum);
	}
	bool hasPathSumRe(TreeNode *root, int value, int sum) {
	if(!root) return false;
	if(!root->left && !root->right){
	if((value+root->val) == sum)
	return true;
	else return false;
	}
	else return hasPathSumRe(root->left, root->val + value, sum)||hasPathSumRe(root->right, root->val + value, sum);
	}
	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
	vector<vector<int> > pathSum(TreeNode *root, int sum) {
	vector<vector<int>> res;
	vector<int> onePossibleSol;
	pathSumRe(root, 0, sum, onePossibleSol, res);
	return res;
	}
	void pathSumRe(TreeNode *root, int value, int sum, vector<int> oneSol, vector<vector<int>> &res) {
	if(!root) return;
	if(!root->left && !root->right){
	if((value+root->val) == sum){
	oneSol.push_back(root->val);
	res.push_back(oneSol);
	}
	else return ;
	}
	oneSol.push_back(root->val);
	pathSumRe(root->left, root->val + value, sum, oneSol, res);
	pathSumRe(root->right, root->val + value, sum, oneSol, res);
	}

view raw gistfile1.cpp hosted with ❤ by GitHub