Google 面试题：二叉树的层次遍历 II

给出一棵二叉树，返回其节点值从底向上的层次序遍历（按从叶节点所在层到根节点所在的层遍历，然后逐层从左往右遍历）

在线评测地址：LintCode 领扣

例1:

输入:
{1,2,3}
输出:
[[2,3],[1]]
解释:
 1
   / \
 2 3
它将被序列化为 {1,2,3}
层次遍历 

例2:

输入:
{3,9,20,#,#,15,7}
输出:
[[15,7],[9,20],[3]]
解释:
    3
   / \
  9  20
    /  \
   15   7
它将被序列化为 {3,9,20,#,#,15,7}
层次遍历 

算法：二叉树的层次遍历

层次遍历，可以运用广度遍历的思想实现从上往下的逐层遍历。从头结点开始逐层遍历，开辟一个新队列，让头结点入队并计算此时的长度，每次都将一层的所有节点压入队列后，得到队列的大小，然后将这这一层的所有点都进行遍历，将从左到右每一个点的子节点都压入队列，将本层节点遍历完后，继续下一层的遍历，然后开始循环，一直遍历到底层，判断的终止条件就是队列为空。

• 循环里面，队列头出队，判断其是否有左右子结点，如果有，则入队，但此时还不需要更新队列的长度，当前队列的长度是每层的长度。当这层的长度减为0时，就说明这层的遍历结束，开始更新长度为下一层的长度。
• 出队的元素的值按照一层层压入结果数组
• 因为题目要求自底向上，那么我们不移动每一层的内容，对层进行倒序

复杂度分析

• 时间复杂度​O(n)​
  • n为树的节点数
• 空间复杂度​O(n)​
  • 保存节点位置 n为树的节点数

public class Solution {
   /**
    * @param root: A tree
    * @return: buttom-up level order a list of lists of integer
    */
   public List<List<Integer>> levelOrderBottom(TreeNode root) {
      // write your code here
      List<List<Integer>> ans = new ArrayList<>();
      LinkedList<TreeNode> queue = new LinkedList<>();
      if (root != null) {
         queue.offer(root);
      }
      //层次遍历
      while (!queue.isEmpty()) {
         int len = queue.size();
         List<Integer> tmpList = new ArrayList<>();
         while (len > 0) {
            TreeNode treeNode = queue.poll();
            tmpList.add(treeNode.val);
            if (treeNode.left != null) { //左子树不为空的话压入队列
               queue.offer(treeNode.left);
            }
            if (treeNode.right != null) {//右子树不为空的话压入队列
               queue.offer(treeNode.right);
            }
            len--;
         }
         ans.add(tmpList);//储存当前层的节点
      }
      //倒序
      Collections.reverse(ans);
      return ans;
   }
}

更多题解参考：九章算法

本文地址：https://blog.csdn.net/JiuZhang_ninechapter/article/details/110182369