107.md

107. Binary Tree Level Order Traversal II

Description

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

For example: Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * Traverse the binary tree with Breadth-First Search (BFS) algorithm
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    "use strict";
    if (!root) {
        return [];
    }
    let result = [[root.val]];
    let queue = [root];
    while (queue.length) {
        let level = [];
        let len = queue.length;
        for (let i = 0; i < len; i++) {
            let left = queue[i].left, right = queue[i].right;
            if (left) {
                queue.push(left);
                level.push(left.val);
            }
            if (right) {
                queue.push(right);
                level.push(right.val);
            }
        }
        level.length && result.push(level);
        queue = queue.slice(len);
    }
    return result.reverse();
};