Leetcode 113. Path Sum II

Problem Explanation

Given a binary tree and a target sum, we need to return all possible root-to-leaf paths where each path's sum is equal to the target sum.

A binary tree is a tree data structure in which each node has at most two children, which are referred as left child and right child. A leaf node of a binary tree is a node without children.

For example, consider a binary tree with 3 levels and target sum 22.

1
2
3      5
4     / \
5    4   8
6   /   / \
7  11  13  4
8 /  \    / \
97    2  5   1

We have two paths summing up to the target sum (22): [5, 4, 11, 2] (from root by left to leaf) and [5, 8, 4, 5] (from root by right to leaf).

Solution Approach

We can solve this problem using Depth-first Search (DFS), a common technique for searching or traversing tree or graph data structures.

We start at the root, and keep traversing the tree depth-wise until we found a leaf node. Along each path, we subtract the value of current node from the target sum, and if it reaches 0 for a leaf node, we record this path.

Then we backtrack to the previous level, and start another path. The process continues until all paths from root to leaf have been explored.

The solution uses recursion, which is a good fit for DFS. A data structure Vector is used to record the current path and all targeting paths.

C++ Solution

1
2c++
3class Solution {
4public:
5    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
6        vector<vector<int>> paths;
7        vector<int> path;
8        findPaths(root, targetSum, path, paths);
9        return paths;
10    }
11private:
12    void findPaths(TreeNode* node, int sum, vector<int>& path, vector<vector<int>>& paths) {
13        if (!node) return;
14        path.push_back(node -> val);
15        if (!(node -> left) && !(node -> right) && sum == node -> val)
16            paths.push_back(path);
17        findPaths(node -> left, sum - node -> val, path, paths);
18        findPaths(node -> right, sum - node -> val, path, paths);
19        path.pop_back();
20    }
21};

Python Solution

1
2python
3class Solution:
4    def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
5        if not root:
6            return []
7        res = []
8        self.dfs(root, target, [], res)
9        return res
10
11    def dfs(self, root, target, path, res):
12        if not root.left and not root.right and target == root.val:
13            path.append(root.val)
14            res.append(path)
15        if root.left:
16            self.dfs(root.left, target-root.val, path+[root.val], res)
17        if root.right:
18            self.dfs(root.right, target-root.val, path+[root.val], res)

Java Solution

1
2java
3class Solution {
4    public List<List<Integer>> pathSum(TreeNode root, int sum) {
5        List<List<Integer>> res = new ArrayList<>();
6        List<Integer> path = new ArrayList<>();
7        dfs(root, sum, res, path);
8        return res;
9    }
10    public void dfs(TreeNode root, int sum, List<List<Integer>> res, List<Integer> path){
11        if(root == null) return; 
12        path.add(root.val);
13        
14        if(root.left == null && root.right == null ){
15            if(root.val == sum)
16                res.add(new ArrayList<>(path));
17        }
18        if(root.left != null) dfs(root.left, sum-root.val, res, path);
19        if(root.right != null) dfs(root.right, sum-root.val, res, path);
20        path.remove(path.size()-1);
21    }
22}

After recursively calling dfs() along the total path sum becomes equal to the target sum path is added to the answer.

Explanation for the C++ Solution

In the beginning, if the provided root is null, It means the tree is empty. So we return an empty vector.

In the dfs function, in the beginning, if the node to be processed is null it indicates that we have reached an end. Hence we return.

We push the value of the current node to path. And then we trigger the dfs function for the left subtree and the right subtree by subtracting the value of the current tree from the current sum.

We keep pushing the node's value which comes in the path from the root to the leaf node to path vector. We keep doing this until we reach the leaf node (leaf node is a node which doesn't have any child nodes).

But for a node, if the processed node is a leaf node and current sum is equal to the node's value, then it means a path from the root to the leaf node via these nodes sum up to be targetSum. Hence we push that path to the paths vector.

After that we pop the current node from the path. Since the remainder sum was not equal to the current node's value. Hence the current node cannot be in any path. Hence we should backtrack. Hence we pop the current node's value from the path.## JavaScript Solution

1
2javascript
3class TreeNode {
4    constructor(val, left, right) {
5        this.val = (val===undefined ? 0 : val)
6        this.left = (left===undefined ? null : left)
7        this.right = (right===undefined ? null : right)
8    }
9}
10
11let pathSum = function(root, sum) {
12    let result = [];
13    if(root === null){
14        return result;
15    }
16    dfs(root, sum,[], result);
17    return result;
18}
19
20let dfs = function(node, remainingSum, path, result) {
21    if(node === null) {
22        return; 
23    }
24    path.push(node.val);
25    
26    if(node.left === null && node.right === null && remainingSum === node.val){
27        result.push(path.slice());
28    }
29    
30    dfs(node.left, remainingSum - node.val, path, result);
31    dfs(node.right, remainingSum - node.val, path, result);
32    
33    path.pop();
34}

Explanation for the JavaScript Solution

In JavaScript, we start by creating a Tree Node constructor to mimic the TreeNode class of Java or C++ and to set up our binary tree.

Then we have the pathSum function which will hold our main logic. In this function we start with checking if the root is null, which means the tree is empty and we return an empty array since there are no paths in an empty tree.

Following that, we use depth-first search(DFS) to traverse the tree by calling our dfs function and passing our root, target sum, an empty array (to store the path), and our results array. At last, we return our result array containing all possible paths that sum up to the target.

In dfs function, we first check if the node is null and return control if it is. Then we add the node's value to the path, and then if it's a leaf node and the sum of the values in the path is equal to the target sum, we then add the copy of the path array to the result. Here, we used the slice() method to create a copy of the path array. If we don't create a copy, any changes we make to the path array later would also modify the array we've just added to our solution set.

Then we make recursive calls to dfs for the left and the right child of the current node, also decrementing the remaining sum by the value of the current node.

After making the recursive calls, we remove the last item from the path since we are done exploring all paths through the current node. This is essentially backtracking to the previous node as we finish the DFS traversal for the subtree under the current node.