二叉树的层序遍历Ⅱ

发表于 更新于 分类于

算法-二叉树的层序遍历Ⅱ

背景

  • 算法–二叉树的层序遍历Ⅱ

  • 博主以代码随想录算法公开课进行学习

题目

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

    示例 1：

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

    示例 2：

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

    示例 3：

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

    提示：

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

思路

  • 二叉树的层序遍历（广度优先遍历 BFS）是解决本题的核心，自底向上的层序遍历可拆解为「正常层序遍历 + 结果逆序」两步：
    • 层序遍历基础：借助队列（Queue/Deque）实现按层访问，队列的先进先出（FIFO）特性可保证 “一层一层处理节点” 的逻辑；
    • 分层处理关键：每次循环前记录当前队列长度（即当前层的节点数），确保仅遍历当前层节点，避免子节点混入当前层遍历；
    • 结果逆序：先通过层序遍历得到 “自顶向下” 的节点值列表，再将列表倒序输出，即可得到 “自底向上” 的遍历结果。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        Deque<TreeNode> que = new LinkedList<>();

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

        que.offerLast(root);
        while(!que.isEmpty()){
            List<Integer> levelList = new ArrayList<>();
            int levelSize = que.size();
            for(int i = 0;i < levelSize;i++){
                TreeNode peek = que.peekFirst();
                levelList.add(que.pollFirst().val);
                if(peek.left != null){
                    que.offerLast(peek.left);
                }
                if(peek.right != null){
                    que.offerLast(peek.right);
                }
            }
            list.add(levelList);
        }
        List<List<Integer>> result = new ArrayList<>();
        for(int i = list.size()-1;i >= 0;i--){
            result.add(list.get(i));
        }
        return result;
    }
}

总结

  • 二叉树层序遍历 Ⅱ 的核心是「BFS 层序遍历 + 结果逆序」，队列是实现层序遍历的关键数据结构；
  • 遍历每层节点前必须记录levelSize（当前层节点数），否则队列中动态加入的子节点会干扰当前层的遍历逻辑；
  • 空树判断是必要的边界处理，可避免NullPointerException，符合算法题 “鲁棒性” 要求；
  • 时间复杂度为 O (n)（n 为节点总数，每个节点仅入队 / 出队一次），空间复杂度为 O (n)（队列最多存储一层节点，最坏情况为满二叉树的最后一层）；
  • 优化思路：可通过result.add(0, levelList)直接将每层结果插入列表头部，省去后续逆序循环，简化代码逻辑。