• 题目
• 大致意思
• 解决方案
• 源代码

题目

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 level order traversal as:
[
  [15,7],
  [9,20],
  [3]
]

大致意思

和102题非常类似。区别在于这道题目是把底层的数组放在最前面。也就是在102题目的答案基础上，进行一次倒转排序。当然，我们肯定不能直接这么干。

解决方案

• 进行遍历，每次遍历，level + 1
• 如果当前的数组的长度小于level的话，我们主动unshift一个空数组放在整个大数组的最前面

if (array.length < level) {
  array.unshift([]);
}

• 由于所有的数据都是根据level来存放，又由于我们是倒转来进行存放，所以 var arr = array[array.length - level];
• 把遍历的当前值push进行 arr.push(root.val);
• 持续遍历

search(root.left, level + 1);
search(root.right, level + 1);

源代码

var levelOrderBottom = function(root) {
  if (!root) return [];
  var array = [];
  search(root, 1);

  function search(root, level) {
    if (root) {
      if (array.length < level) {
        array.unshift([]);
      }

      var arr = array[array.length - level];
      arr.push(root.val);
      search(root.left, level + 1);
      search(root.right, level + 1)
    } else {
      return;
    }
  }

  return array;
};