[Leetcode] 112. Path Sum

112. Path Sum

Given the rootof a binary tree and an integer targetSum, return trueif the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There are two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

Example 3:

Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.

Constraints:

The number of nodes in the tree is in the range [0, 5000].

-1000 <= Node.val <= 1000

-1000 <= targetSum <= 1000

How to understand?

Find the root-to-leaf path exists that meets the sum of targetSum. if it is found then return true, if it is not found then return false. The leaf node means the node without its children.

How to approach?

Recursion

function hasPathSum(root: TreeNode | null, sum: number): boolean {
    if (root === null) return false;
    sum -= root.val;
    if (root.left === null && root.right === null)
        return sum === 0;
    return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
}

sum will be changed by subtracting the node's value.

and when there is no left and right node for the node(when both are null value), return the boolean that checks if the sum is 0.

when it has left and right node, call the hasPathSum function recursively for both node.

Iteration

function hasPathSum(root: TreeNode | null, sum: number): boolean {
    if (!root) return false;
    let nodeStack: TreeNode[] = [];
    let sumStack: number[] = [];
    nodeStack.push(root);
    sumStack.push(sum - root.val);
    while (nodeStack.length > 0) {
        let currentNode = nodeStack.pop();
        let currSum = sumStack.pop();
        if (!currentNode!.left && !currentNode!.right && currSum === 0)
            return true;
        if (currentNode!.right) {
            nodeStack.push(currentNode!.right);
            sumStack.push(currSum! - currentNode!.right.val);
        }
        if (currentNode!.left) {
            nodeStack.push(currentNode!.left);
            sumStack.push(currSum! - currentNode!.left.val);
        }
    }
    return false;
}

create nodeStack and sumStack.

push the root to nodeStack and sum-root.val to sumStack.

create while condition to check if the nodeStack has length.

set currentNode and currSum from each array. pop the last element.

if the currentNode doesn't have left and right node and currSum is 0 then it means if found the root-to-leaf path that meets targetSum value. so return true.

and for each left node and right node, push the node and sum value that is calculated by subtracting the node value.

if there is nothing in the nodeStack and there was no found root-to-leaf path that meets the targetSum, return false.