0113. Path Sum II

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where each path's sum equals targetSum.

A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: []

Example 3:

Input: root = [1,2], targetSum = 0
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

Analysis

Similar to path sum, this question requires us to return all the paths, so we need to maintain the path along with the recursion calls.

• Time: $O(n^2)$ because for each push_back to the res, it will require path.size() operation.
• Space: $O(n)$ if don't count the return space.

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> res;

    void dfs(TreeNode* root, int sum, vector<int> path) {
        if (!root) return ;
        sum -= root -> val;
        path.push_back(root -> val);
        if (!sum && !root -> left && !root -> right) {
            res.push_back(path);
            return ;
        }
        dfs(root -> left, sum, path);
        dfs(root -> right, sum, path);
    }

    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        dfs(root, sum, {});
        return res;
    }
};

---

Last update: April 1, 2022