107. Binary Tree Level Order Traversal II

Leetcode

https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

題目

Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

解答

• 方法一

Same as Question 102. -> Just add .reverse() when return the value

var levelOrderBottom = function(root) {
    if(root === null) return [];
    
    const res = [];
    const helper = (node, level) => {
        if (res[level]) {
            res[level].push(node.val);
        } else {
            res[level] = [node.val];
        }
        
        if (node.left) {
            helper(node.left, level + 1);
        }
        if (node.right) {
            helper(node.right, level + 1);
        }  
    }
    
    helper(root, 0);
    return res.reverse();  
};

Runtime: 86 ms, faster than 58.13% of JavaScript online submissions for Binary Tree Level Order Traversal II.

Memory Usage: 44.7 MB, less than 11.31% of JavaScript online submissions for Binary Tree Level Order Traversal II.

• 方法二

var levelOrderBottom = function(root) {
    if(root === null) return [];
    
    const res = [];
    const queue = [root];
    let level = 0;
    while(queue.length) {
        const len = queue.length;
        res.push([]);
        for(let i=0; i<len; i++) {
            const node = queue.shift();
            res[level].push(node.val);
            if(node.left) queue.push(node.left);
            if(node.right) queue.push(node.right);
        }
        level++;
    }
    
    return res.reverse();  
};

Runtime: 96 ms, faster than 46.82% of JavaScript online submissions for Binary Tree Level Order Traversal II.

Memory Usage: 44 MB, less than 59.89% of JavaScript online submissions for Binary Tree Level Order Traversal II.