Back to DSA

Path Sum II

medium
Acceptance: 50%
Binary Tree

Given a binary tree and a target sum, enumerate all paths from the root to a leaf where the node values along the path add up exactly to the target. Return each qualifying path as a list of node values.

Examples

Example 1:
Input:root = [10,5,15,3,7,null,20], targetSum = 18
Output:[[10,5,3]]
Example 2:
Input:root = [1,2,3], targetSum = 3
Output:[[1,2]]

Hints

Related Problems

Maximum Depth of Binary TreeeasyInvert Binary TreeeasyValidate Binary Search TreemediumLowest Common Ancestor of a Binary TreemediumBinary Tree Level Order Traversalmedium
00:00
import java.util.*;

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, targetSum, new ArrayList<>(), result);
        return result;
    }

    private void dfs(TreeNode node, int remain, List<Integer> path, List<List<Integer>> result) {
        if (node == null) return;
        path.add(node.val);
        if (node.left == null && node.right == null && remain == node.val) {
            result.add(new ArrayList<>(path));
        }
        dfs(node.left, remain - node.val, path, result);
        dfs(node.right, remain - node.val, path, result);
        path.remove(path.size() - 1);
    }
}
Time complexityO(n^2)
Space complexityO(n)