113. Path Sum II – Leetcode Solutions

July 3, 2024

Table of Contents

Description:

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

Examples:

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]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

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

Example 3:

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

Solution in Python:

To solve the problem of finding all root-to-leaf paths where the sum of node values equals the target sum in a binary tree, we can use a Depth-First Search (DFS) approach.

Python

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        # This list will hold all the paths that sum up to targetSum
        all_paths = []
        
        # Helper function to perform DFS on the tree
        def dfs(node, current_path, current_sum):
            if not node:
                return
            
            # Add the current node's value to the path and update the current sum
            current_path.append(node.val)
            current_sum += node.val
            
            # If the current node is a leaf and its path sums up to targetSum, add the path to all_paths
            if not node.left and not node.right and current_sum == targetSum:
                all_paths.append(list(current_path))
            else:
                # Recur on the left and right subtrees
                dfs(node.left, current_path, current_sum)
                dfs(node.right, current_path, current_sum)
            
            # Backtrack by removing the current node's value from the path
            current_path.pop()
        
        # Start DFS with an empty path and a sum of 0
        dfs(root, [], 0)
        
        return all_paths

Detailed Comments:

TreeNode Class Definition:
- The TreeNode class defines the structure of a node in a binary tree.
- Each node has an integer value (val), a left child (left), and a right child (right).
pathSum Method:
- Input Parameters: The method takes two parameters: root, which is the root of the binary tree, and targetSum, which is the target sum we are looking for in the root-to-leaf paths.
- The method initializes an empty list all_paths that will store all the valid paths.
dfs Helper Function:
- Parameters: This function takes three parameters: the current node, the current path (current_path), and the current sum (current_sum).
- Base Case: If the current node is null, we return immediately.
- Update Path and Sum: We add the current node’s value to current_path and update current_sum with the node’s value.
- Leaf Node Check: If the current node is a leaf (i.e., it has no left or right children) and the current_sum equals targetSum, we add a copy of current_path to all_paths.
- Recursive Calls: We recursively call dfs on the left and right children of the current node.
- Backtracking: After exploring both subtrees, we backtrack by removing the current node’s value from current_path to explore other potential paths.
Returning the Result:
- The pathSum method starts the DFS by calling dfs with the root node, an empty path, and an initial sum of 0.
- Finally, it returns the all_paths list containing all the paths that sum to the target sum.

This approach ensures that all root-to-leaf paths are explored, and only those paths that meet the target sum are collected and returned. The time complexity is O(n), where nnn is the number of nodes in the tree, as each node is visited once. The space complexity is O(h), where hhh is the height of the tree, representing the maximum depth of the recursion stack and the maximum path length stored.

Solution in Javascript:

JavaScript

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number[][]}
 */
var pathSum = function(root, targetSum) {
    // This array will hold all the paths that sum up to targetSum
    const allPaths = [];
    
    /**
     * Helper function to perform DFS on the tree
     * @param {TreeNode} node - the current node
     * @param {number[]} currentPath - the current path from the root to this node
     * @param {number} currentSum - the sum of the values in currentPath
     */
    function dfs(node, currentPath, currentSum) {
        if (!node) {
            return;
        }
        
        // Add the current node's value to the path and update the current sum
        currentPath.push(node.val);
        currentSum += node.val;
        
        // If the current node is a leaf and its path sums up to targetSum, add the path to allPaths
        if (!node.left && !node.right && currentSum === targetSum) {
            allPaths.push([...currentPath]);
        } else {
            // Recur on the left and right subtrees
            dfs(node.left, currentPath, currentSum);
            dfs(node.right, currentPath, currentSum);
        }
        
        // Backtrack by removing the current node's value from the path
        currentPath.pop();
    }
    
    // Start DFS with an empty path and a sum of 0
    dfs(root, [], 0);
    
    return allPaths;
};

Solution in Java:

Java

import java.util.*;


class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> allPaths = new ArrayList<>();
        List<Integer> currentPath = new ArrayList<>();
        dfs(root, targetSum, currentPath, allPaths);
        return allPaths;
    }
    
    /**
     * Helper method to perform DFS and find all root-to-leaf paths
     * @param node Current node in traversal
     * @param remainingSum Remaining sum to achieve targetSum
     * @param currentPath Current path from root to current node
     * @param allPaths List to collect all paths that sum to targetSum
     */
    private void dfs(TreeNode node, int remainingSum, List<Integer> currentPath, List<List<Integer>> allPaths) {
        if (node == null) {
            return;
        }
        
        // Add current node to the path
        currentPath.add(node.val);
        
        // Check if this is a leaf node and if the current path sums up to targetSum
        if (node.left == null && node.right == null && node.val == remainingSum) {
            // Add a copy of currentPath to allPaths (Java passes references, so we need to create a copy)
            allPaths.add(new ArrayList<>(currentPath));
        } else {
            // Recur on the left subtree
            dfs(node.left, remainingSum - node.val, currentPath, allPaths);
            // Recur on the right subtree
            dfs(node.right, remainingSum - node.val, currentPath, allPaths);
        }
        
        // Backtrack: Remove current node from currentPath to explore other paths
        currentPath.remove(currentPath.size() - 1);
    }
}

Solution in C#:

C#

using System.Collections.Generic;

public class Solution {
    public IList<IList<int>> PathSum(TreeNode root, int targetSum) {
        List<IList<int>> allPaths = new List<IList<int>>();
        List<int> currentPath = new List<int>();
        Dfs(root, targetSum, currentPath, allPaths);
        return allPaths;
    }
    
    /**
     * Helper method to perform DFS and find all root-to-leaf paths
     * @param node Current node in traversal
     * @param remainingSum Remaining sum to achieve targetSum
     * @param currentPath Current path from root to current node
     * @param allPaths List to collect all paths that sum to targetSum
     */
    private void Dfs(TreeNode node, int remainingSum, List<int> currentPath, List<IList<int>> allPaths) {
        if (node == null) {
            return;
        }
        
        // Add current node to the path
        currentPath.Add(node.val);
        
        // Check if this is a leaf node and if the current path sums up to targetSum
        if (node.left == null && node.right == null && node.val == remainingSum) {
            // Add a copy of currentPath to allPaths (C# passes references, so we need to create a copy)
            allPaths.Add(new List<int>(currentPath));
        } else {
            // Recur on the left subtree
            Dfs(node.left, remainingSum - node.val, currentPath, allPaths);
            // Recur on the right subtree
            Dfs(node.right, remainingSum - node.val, currentPath, allPaths);
        }
        
        // Backtrack: Remove current node from currentPath to explore other paths
        currentPath.RemoveAt(currentPath.Count - 1);
    }
}

113. Path Sum II – Leetcode Solutions

Description:

Solution in Python:

Detailed Comments:

Solution in Javascript:

Solution in Java:

Solution in C#:

Popular

185. Department Top Three Salaries – Leetcode Solutions

6. Zigzag Conversion – Leetcode Solutions

188. Best Time to Buy and Sell Stock IV – Leetcode Solutions

67. Add Binary – Leetcode Solutions

90. Subsets II – Leetcode Solutions

204. Count Primes – Leetcode Solutions

73. Set Matrix Zeroes – Leetcode Solutions

113. Path Sum II – Leetcode Solutions

Description:

Solution in Python:

Detailed Comments:

Solution in Javascript:

Solution in Java:

Solution in C#:

Related Post

Popular