# missjing/leetcode

Switch branches/tags
Nothing to show
Fetching contributors…
Cannot retrieve contributors at this time
54 lines (48 sloc) 1.12 KB
 problem: 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 binary tree struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; void pathSum_aux(TreeNode *root, int sum, vector > &ret, vector &tmp) { if(root == NULL) return; tmp.push_back(root->val); int leftsum = sum - root->val; if(leftsum == 0 && root->left == NULL && root->right == NULL) { ret.push_back(tmp); } pathSum_aux(root->left, leftsum, ret, tmp); pathSum_aux(root->right, leftsum, ret, tmp); tmp.pop_back(); } vector > pathSum(TreeNode *root, int sum) { vector > ret; if(root == NULL) return ret; vector tmp; pathSum_aux(root, sum, ret, tmp); return ret; }