113. 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.

Note: A leaf is a node with no children.

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

void helper(TreeNode* node, int sum, vector<int>& cur, vector<vector<int> >& res) {
    if (!node) return;
    cur.push_back(node->val);
    if (!node->left && !node->right && node->val == sum) {
        res.push_back(cur);
    }
    if (node->left) {
        helper(node->left, sum - node->val, cur, res);
    }
    if (node->right) {
        helper(node->right, sum - node->val, cur, res);
    }
    cur.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
    vector<vector<int> > res;
    if (!root) return res;
    vector<int> cur;
    helper(root, sum, cur, res);
    return res;
}