LeetCode 113:Path Sum II

Datetime:2016-08-23 01:23:32          Topic: LeetCode           Share

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

Subscribe to see which companies asked this question

class Solution {
 public:
	 vector<vector<int>> pathSum(TreeNode* root, int sum) {
		 vector<vector<int>> res;
		 vector<int> tmp; //保存中间结果
		 tmpFunction(root, sum, tmp, res);
		 return res;
	 }

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




About List