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]

]

struct Node { int val; Node *left; Node *right; Node(int v) { val = v; left = right = NULL; } }; void visit(Node *root, int target, int sum, vector<int> &a, vector<vector<int> > &result) { if (root == NULL) { return; } sum += root->val; a.push_back(root->val); if (root->left == NULL && root->right == NULL) { if (sum == target) { result.push_back(a); } } else { visit(root->left, target, sum, a, result); visit(root->right, target, sum, a, result); } a.pop_back(); } vector<vector<int> > fun(Node *root, int target) { vector<vector<int> > result; vector<int> a; visit(root, target, 0, a, result); return result; }