113. Path Sum II

Path Sum II

Problem Description

Given the root of a binary tree and an integer, 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.

 

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: []

 

Constraints:

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

Idea:

This problem is to find sets, not evaluate, but to enumerate all possibilities, so dynamic programming is not particularly suitable, so we need to consider other methods.

In fact, there is a general solution to this problem, which is the backtracking method. There are also great gods on the Internet who have given the general, and all the solutions here are solved using the general method. In addition to this question, there are many other questions that can use this general solution. For specific questions, see the related questions section below.

The specific code of the general writing method is shown in the code area below.

Analysis of key points

Backtracking

backtrack problem-solving formula

A) BackTracking 

Let`s Code IT!

/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
var pathSum = function(root, sum) {
  if (root === null) return [];
  const res = [];
  backtrack(root, sum, res, []);
  return res;
};

function backtrack(root, sum, res, tempList) {
  if (root === null) return;
  if (root.left === null && root.right === null && sum === root.val)
    return res.push([...tempList, root.val]);

  tempList.push(root.val);
  backtrack(root.left, sum - root.val, res, tempList);

  backtrack(root.right, sum - root.val, res, tempList);
  tempList.pop();
}

B) Using Recursion (Just another way to write)

Let`s Code IT!

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
var pathSum = function(root, sum) {
    var result = [];
    
    if (!root) {
        return result;
    }
    
    genPath(result, root, [], 0, sum);
    
    return result;
};

function genPath(result, root, curArr, curSum, target) {
    curArr.push(root.val);
    curSum += root.val;
    
    if ((curSum === target) && !root.left && !root.right) {
        result.push(curArr);
        return;
    }
    
    if (root.left) {
        genPath(result, root.left, curArr.concat(), curSum, target);
    }
    
    if (root.right) {
        genPath(result, root.right, curArr.concat(), curSum, target);
    }
}

Conclusion

That’s all folks! In this post, we solved LeetCode problem #113. Path Sum II

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!