129. Sum Root to Leaf Numbers

Leetcode

https://leetcode.com/problems/sum-root-to-leaf-numbers/

題目

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

• For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

Example 1:

Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

解答

• 方法一

Recursion

var sumNumbers = function(root) {
    if(root === null) return 0;
    
    const res = []
    
    const helper = (node, number) => {
        const val = node.val;
        const nextNumber = (number + val.toString()).toString();
        
        if (!node.left && !node.right) {
            res.push(nextNumber);
        }
        if (node.left) {
            helper(node.left, nextNumber);
        }
        if (node.right) {
            helper(node.right, nextNumber);
        }
    }
    
    helper(root, '0');
    const sum = res.reduce((accu, curr) => {
        return accu + +curr;
    }, 0)
    return sum;
};

Runtime: 70 ms, faster than 75.20% of JavaScript online submissions for Sum Root to Leaf Numbers.

Memory Usage: 42 MB, less than 84.83% of JavaScript online submissions for Sum Root to Leaf Numbers.

• 方法二

Iteration

var sumNumbers = function(root) {
    if (!root) return 0;
    
    const res = [];
    const queue = [{
        node: root,
        val: ''
    }];
    while (queue.length) {
        const curr = queue.shift();
        const node = curr.node;
        const nodeVal = node.val;
        const nextVal = (curr.val + nodeVal.toString()).toString();
        
        if (!node.left && !node.right) {
            res.push(+nextVal);
        }
        if (node.left) {
            queue.push({
                node: node.left,
                val: nextVal
            })
        }
        if (node.right) {
            queue.push({
                node: node.right,
                val: nextVal
            })
        }
    }
    
    const sum = res.reduce((accu, curr) => {
        return accu + curr;
    }, 0)
    return sum;
};

Runtime: 64 ms, faster than 90.68% of JavaScript online submissions for Sum Root to Leaf Numbers.

Memory Usage: 42.6 MB, less than 39.49% of JavaScript online submissions for Sum Root to Leaf Numbers.