Pengjielee's blog

题目

给定一个二叉树，返回其节点值自底向上的层序遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：

给定二叉树 [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7

返回其自底向上的层序遍历为：
[
  [15,7],
  [9,20],
  [3]
]

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

JS实现

1、反转其返回结果（102.二叉树的层序遍历）

/**
 * 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 result = [];

  if (root === null) {
    return result;
  }

  // 声明一个队列，队列特点：先进先出
  let q = [];
  // 入队根节点
  q.push(root);

  while (q.length > 0) {
    // 层次数组
    const level = [];
    const len = q.length;

    // 遍历队列
    for (let i = 0; i < len; i++) {
      // 出队
      const node = q.shift();
      // 保存节点值 到 层次数组
      level.push(node.val);

      // 左节点入队
      if (node.left != null) {
        q.push(node.left);
      }
      // 右节点入队
      if (node.right != null) {
        q.push(node.right);
      }
    }

    // 保存 每层数组 到结果
    result.push(level);
  }

  return result.reverse();
};

2、unshift方法

var levelOrderBottom = function (root) {
  const result = [];

  if (root === null) {
    return result;
  }

  // 声明一个队列，队列特点：先进先出
  let q = [];
  // 入队根节点
  q.push(root);

  while (q.length > 0) {
    // 层次数组
    const level = [];
    const len = q.length;

    // 遍历队列
    for (let i = 0; i < len; i++) {
      // 出队
      const node = q.shift();
      // 保存节点值 到 层次数组
      level.push(node.val);

      // 左节点入队
      if (node.left != null) {
        q.push(node.left);
      }
      // 右节点入队
      if (node.right != null) {
        q.push(node.right);
      }
    }

    // 保存 每层数组 到结果（unshift在开头插入）
    result.unshift(level);
  }

  return result;
};