Binary Tree Level Order Traversal II

Problem

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

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    const queue = root ? [root] : [];
    const res = [];

    while (queue.length) {
        const n = queue.length;
        const list = [];
        for (i = 0; i < n; i++) {
            const node = queue.shift();
            list.push(node.val);

            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
        }
        res.push(list);
    }
    return res.reverse();
};

We will implement a BFS solution. This solution is almost identical to Binary Tree Level Order Traversal. The only difference is that we need to reverse res before returning it. Note that if we want to avoid reversing, another method is to find the height of root first, so we can compute the index of each level in res.

Problem​

Solution​

Problem

Solution