107.二叉树的层序遍历Ⅱ

难度：中等

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

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

翻转法

这道题和 102 题的差别，只在于输出结果的顺序刚好相反，那么我的第一想法是，直接调用 Collections.reverse 函数来翻转最终的数组即可。

层序遍历一个二叉树。就是从左到右、一层一层地去遍历二叉树。这种遍历的方式需要借用一个辅助数据结构即队列来实现。

队列具有 先进先出 的特性，符合层序遍历的逻辑。这种层序遍历的方式就是图论中的广度优先遍历，只不过我们应用在了二叉树上。

算法流程：

处理特例：若根节点为空，则返回空列表
根节点入队
BFS 循环：判断队列是否为空。如果不为空，说明还有节点需要遍历
1. 初始化当前层的节点个数 currentLevelSize 为队列的大小。
2. 首先初始化一个空的列表 currentLevelList 用于存储当前层的节点值。
3. 使用一个内层循环，遍历当前层的节点。循环次数为当前层的节点个数 currentLevelSize。
  1. 从队列中取出一个节点 current，将其值添加到 currentLevelList 中。
  2. 如果当前节点有左子节点，将左子节点入队。
  3. 如果当前节点有右子节点，将右子节点入队。
4. 将存储当前层节点值的列表 currentLevelList 添加到结果列表 result 中。
5. 此时队列中已经把当前层的节点都出队了，同时把下一层的节点都入队了，因此队列大小刚好变成了下一层的节点个数。
翻转结果列表
返回结果列表

代码展示

java

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    // 若根节点为空，则返回空列表
    if (root == null) {
        return result;
    }
    Deque<TreeNode> queue = new LinkedList<>();
    // 根节点入队
    queue.add(root);
    // BFS 循环
    while (!queue.isEmpty()) {
        int currentLayerSize = queue.size();
        List<Integer> currentLayerList  = new ArrayList<>();
        // 这里一定要使用固定大小currentLayerSize，不要使用queue.size()，因为queue不停地出队入队，所以其大小是不断变化的
        for (int i = 0; i < currentLayerSize; i++) {
            TreeNode current = queue.poll();
            currentLayerList.add(current.val);

            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
        }
        result.add(currentLayerList);
    }
    // 翻转结果列表
    Collections.reverse(result);
    return result;
}

时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

空间复杂度：O(n)，最差情况下，即当树为满二叉树时，最多有 (n+1)/2 个树节点同时在 queue 中，故使用 O(n) 大小的额外空间。

不翻转法

利用链表可以进行 O(1) 头部插入，这样最后的答案就不需要再翻转了。

注意 addFirst() 是 LinkedList 类的方法，List 接口只有 add() 方法。

代码展示

java

public List<List<Integer>> levelOrderBottom(TreeNode root) {
    // 利用链表可以进行 O(1) 头部插入, 这样最后答案不需要再反转
    LinkedList<List<Integer>> result = new LinkedList<>();
    // 若根节点为空，则返回空列表
    if (root == null) {
        return result;
    }
    Deque<TreeNode> queue = new LinkedList<>();
    // 根节点入队
    queue.add(root);
    // BFS 循环
    while (!queue.isEmpty()) {
        int currentLayerSize = queue.size();
        List<Integer> currentLayerList = new ArrayList<>();
        // 这里一定要使用固定大小currentLayerSize，不要使用queue.size()，因为queue不停地出队入队，所以其大小是不断变化的
        for (int i = 0; i < currentLayerSize; i++) {
            TreeNode current = queue.poll();
            currentLayerList.add(current.val);

            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
        }
        result.addFirst(currentLayerList);
    }
    return result;
}

时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

空间复杂度：O(n)，最差情况下，即当树为满二叉树时，最多有 (n+1)/2 个树节点同时在 queue 中，故使用 O(n) 大小的额外空间。

总结

在链表头部插入数据的时间复杂度是 O(1)。

107.二叉树的层序遍历Ⅱ ​

翻转法 ​

代码展示 ​

不翻转法 ​

代码展示 ​

总结 ​

107.二叉树的层序遍历Ⅱ

翻转法

代码展示

不翻转法

代码展示

总结