113. Path Sum II

Leetcode

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

題目

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.

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

解答

• 方法一

Recursion

var pathSum = function(root, targetSum) {
    if (!root) return [];
    
    const res = [];
    
    const helper = (node, remain, arr) => {
        const nodeVal = node.val;
        remain = remain - nodeVal;
        const nextArr = [...arr, nodeVal];
        
        if (!node.left && !node.right) {
            if (remain === 0) res.push(nextArr);
        }
        if (node.left) {
            helper(node.left, remain, nextArr)
        }
        if (node.right) {
            helper(node.right, remain, nextArr)
        }
    }
    
    helper(root, targetSum, []);
    return res;
};

Runtime: 72 ms, faster than 95.87% of JavaScript online submissions for Path Sum II.

Memory Usage: 54.3 MB, less than 18.88% of JavaScript online submissions for Path Sum II.

• 方法二

Iteration

var pathSum = function(root, targetSum) {
    if (!root) return [];
    
    const res = [];
    const queue = [{
        node: root,
        remain: targetSum,
        arr: []
    }];
    while (queue.length) {
        const curr = queue.shift();
        const node = curr.node;
        const nodeVal = node.val;
        const remain = curr.remain - nodeVal;
        const nextArr = [...curr.arr, nodeVal];
        
        if (!node.left && !node.right) {
            if (remain === 0) res.push(nextArr);
        }
        if (node.left) {
            queue.push({
                node: node.left,
                remain,
                arr: nextArr
            })
        }
        if (node.right) {
            queue.push({
                node: node.right,
                remain,
                arr: nextArr
            })
        }
    }
    
    return res;
};

Runtime: 118 ms, faster than 45.43% of JavaScript online submissions for Path Sum II.

Memory Usage: 49 MB, less than 50.15% of JavaScript online submissions for Path Sum II.