算法

(二叉树的层次遍历) $O(n)$

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

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

Java 代码

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
         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;
    }
}