DevExCode

LeetCode 113: Path Sum II Solution

Master LeetCode problem 113 (Path Sum II), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation

To solve this problem, we can use a depth-first search (DFS) algorithm to traverse the binary tree from the root to each leaf node. During the traversal, we keep track of the current path and its sum. If we reach a leaf node and the sum equals the target sum, we add the current path to the result.

  • Start with an empty result list to store the valid paths.
  • Implement a recursive DFS function that takes the current node, the current path, and the current sum as parameters.
  • At each node, update the current path and sum, then check if it's a leaf node and if the sum equals the target sum. If so, add the path to the result.
  • Recursively call the function for the left and right child nodes.
  • Finally, return the result containing all valid paths.

Time Complexity: O(n), where n is the number of nodes in the binary tree. We visit each node once.

Space Complexity: O(n) in the worst-case scenario when the binary tree is skewed. The space is used for the recursion stack.

Solution Code

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> paths = new ArrayList<>();
        List<Integer> currentPath = new ArrayList<>();
        dfs(root, targetSum, currentPath, paths);
        return paths;
    }
    
    private void dfs(TreeNode node, int targetSum, List<Integer> currentPath, List<List<Integer>> paths) {
        if (node == null) return;
        
        currentPath.add(node.val);
        
        if (node.left == null && node.right == null && node.val == targetSum) {
            paths.add(new ArrayList<>(currentPath));
        } else {
            dfs(node.left, targetSum - node.val, currentPath, paths);
            dfs(node.right, targetSum - node.val, currentPath, paths);
        }
        
        currentPath.remove(currentPath.size() - 1);
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 113 (Path Sum II)?

This page provides optimized solutions for LeetCode problem 113 (Path Sum II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 113 (Path Sum II)?

The time complexity for LeetCode 113 (Path Sum II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 113 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 113 in Java, C++, or Python.

Back to LeetCode Solutions