二叉树的层序遍历

发表于 更新于 分类于

算法-二叉树的层序遍历

背景

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

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

题目

  • 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

    示例 1：

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

    示例 2：

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

    示例 3：

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

    提示：

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

思路

  • 二叉树的层序遍历（也叫广度优先遍历 BFS）的核心是按层访问，需要借助队列这个数据结构来实现：
    • 初始化队列，将根节点入队；
    • 循环处理队列：每次取出当前队列中所有节点（即当前层的所有节点），记录它们的值；
    • 同时将当前层每个节点的左、右子节点（非空）依次入队，作为下一层的待处理节点；
    • 重复上述步骤直到队列为空，最终得到按层划分的节点值列表。

代码实现

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
48
/**
 * 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>> resList = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
            checkFun(root);
            return resList;
    }

           public void checkFun(TreeNode node){
            if(node == null) return;// 空树直接返回
            Queue<TreeNode> que = new LinkedList<TreeNode>();// 队列存储节点（LinkedList实现Queue）
            que.offer(node);// 根节点入队

            while(!que.isEmpty()){
                List<Integer> itemList = new ArrayList<Integer>();//存储当前层的节点值
                int len = que.size();

                while(len>0){
                    TreeNode tmpNode = que.poll();
                    itemList.add(tmpNode.val);
                    if(tmpNode.left != null){
                        que.offer(tmpNode.left);
                    }
                    if(tmpNode.right != null){
                        que.offer(tmpNode.right);
                    }
                    len--;
                }
                resList.add(itemList);

            }
        
        }
}

总结

  • 二叉树层序遍历的核心是队列 + 分层处理：用队列缓存节点，通过记录每层节点数实现分层；
  • 关键步骤：根节点入队 → 遍历当前层所有节点（记录值 + 子节点入队） → 保存当前层结果 → 重复至队列为空；
  • 空树判断是必要的边界处理，避免程序异常。