112. Path Sum

Leetcode

https://leetcode.com/problems/path-sum/

題目

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

解答

• 方法一

Recursion

var hasPathSum = function(root, targetSum) {    
    if (!root) return false;
    const val = targetSum - root.val;

    if (!root.left && !root.right) {
        return val === 0;
    }
    return hasPathSum(root.left, val) || hasPathSum(root.right, val);
};

Runtime: 79 ms, faster than 80.83% of JavaScript online submissions for Path Sum.

Memory Usage: 45.7 MB, less than 40.85% of JavaScript online submissions for Path Sum.

• 方法二

Iteration

var hasPathSum = function(root, targetSum) {
    if (root === null) return false;
    
    const res = [];
    const queue = [{
        val: targetSum - root.val,
        node: root
    }];
    while (queue.length) {
        const curr = queue.shift();        
        const val = curr.val;
        const node = curr.node;
        
        if (!node.left && !node.right) {
            if (val === 0) return true;
        }
        if (node.left) {
            queue.push({
                val: val - node.left.val,
                node: node.left
            })
        }
        if (node.right) {
            queue.push({
                val: val - node.right.val,
                node: node.right
            })
        }
    }
    
    return false;
};

Runtime: 96 ms, faster than 58.14% of JavaScript online submissions for Path Sum.

Memory Usage: 47 MB, less than 5.28% of JavaScript online submissions for Path Sum.