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

---

Also the same idea as the Path Sum, additionally, we can use a vector to record the search path. If we find one path, push the path to the final result.

C++ Code:

/*
 * func: find_all_path_helper
 * goal: helper function to traverse the tree recursively
 * @param root: root node of the tree
 * @param sum: current sum needed
 * @param result: final result set
 * @param candidate: current candidate path
 * return:
 */
void find_all_path_helper(TreeNode *root, int sum, vector<vector<int> > &result, vector<int> candidate){
    if(root == nullptr){
        return;
    }
    if(root->left == nullptr && root->right == nullptr){
        if(root->val == sum){
            candidate.emplace_back(root->val);
            result.emplace_back(candidate);
            return;
        }else{
            return;
        }
    }else{
        candidate.emplace_back(root->val);
        find_all_path_helper(root->left, sum-root->val, result, candidate);
        find_all_path_helper(root->right, sum-root->val, result, candidate);
    }
}

/*
 * func: find_all_path
 * goal: find all paths that sum up to the given
 * @param root: root node of the tree
 * @param sum: given sum
 */
vector<vector<int> > find_all_path(TreeNode *root, int sum){
    vector<vector<int> > result;
    vector<int> candidate;
    find_all_path_helper(root, sum, result, candidate);
    return result;
}

Python Code:

# func: find all paths from root to leaf that sum up to the given
# @param root: root node of the tree
# @param sum: given sum
# @return: all paths
def find_all_path(root, sum):
    result = []
    def find_all_path_helper(node, sum, candidate):
        if not node:
            return
        elif not node.left and not node.right:
            if node.val == sum:
                candidate.append(node.val)
                result.append(candidate)
            return
        else:
            find_all_path_helper(node.left, sum-node.val, candidate[:]+[node.val])
            find_all_path_helper(node.right, sum-node.val, candidate[:]+[node.val])

    find_all_path_helper(root, sum, [])
    return result