107. Binary Tree Level Order Traversal II

Problem

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 1

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

var helper = function (root, level, res) {
  if (!root) return;
  if (!res[level]) res[level] = [];
  res[level].push(root.val);
  helper(root.left, level + 1, res);
  helper(root.right, level + 1, res);
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).

Solution 2

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

var helper = function (root, level, res) {
  if (!root) return;
  if (res.length < level + 1) res.unshift([]);
  res[res.length - level - 1].push(root.val);
  helper(root.left, level + 1, res);
  helper(root.right, level + 1, res);
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).

Solution 3

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

  while (stack.length) {
    [node, level] = stack.pop();
    if (node) {
      if (res.length < level + 1) res.unshift([]);
      res[res.length - level - 1].push(node.val);
      stack.push([node.right, level + 1]);
      stack.push([node.left, level + 1]);
    }
  }

  return res;
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).

Solution 4

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

  while (queue.length) {
    [node, level] = queue.shift();
    if (node) {
      if (res.length < level + 1) res.unshift([]);
      res[res.length - level - 1].push(node.val);
      queue.push([node.left, level + 1]);
      queue.push([node.right, level + 1]);
    }
  }

  return res;
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).