数据结构与算法 / 系统课时

用层序遍历处理树的分层信息

用层序遍历处理树的分层信息

当题目要求“按层”观察二叉树时,关键不是记住 BFS 模板,而是明确每一层的边界。做法是在处理一层前先记录队列长度,用这段固定数量的节点计算本层答案,再让它们的子节点进入下一层。

学习目标

  • 用队列长度准确划分二叉树的层级边界
  • 把同一套层序框架改造成层平均值、右视图和最短深度
  • 避免把下一层节点误算进当前层

为什么队列能表示一层

层序遍历使用先进先出的队列。开始处理某一层时,队列里恰好保存这一层尚未访问的节点;访问这些节点的过程中,它们的左右孩子会继续入队,因此队列内容会逐渐混入下一层。

所以不能写成“队列不空就一直处理,期间顺便统计当前层”。正确做法是先保存 levelSize = queue.size(),随后只弹出这 levelSize 个节点。即使队列长度继续增长,本轮循环的边界也不会改变。

层序遍历中用队列长度锁定每层边界

主示例:计算每层平均值

下面用完整 Java 程序计算二叉树每层节点值的平均数。核心步骤只有三个:记录当前层大小、累计这一层的值、把孩子加入队列。

java
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class LevelAverageDemo {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    static List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            long sum = 0;

            // 只处理本轮开始时已经在队列中的节点。
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                sum += node.val;

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            result.add((double) sum / levelSize);
        }

        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        System.out.println(averageOfLevels(root));
    }
}

预期输出:

text
[3.0, 14.5, 11.0]

这里用 long 保存层和,避免节点值较大或一层节点较多时先发生整数溢出;真正做除法时再转成 double。

同一框架如何切换题型

层平均值需要看完整层,所以在这一层的循环中累计总和,并在循环结束后计算平均值。

二叉树右视图只关心每层最后一个节点。只要在 i == levelSize - 1 时记录当前节点,就能得到从右侧看到的序列;这里依赖的不是“先访问右子树”,而是“知道这一层在哪里结束”。

最短深度关心第一次遇到叶子节点的层数。BFS 按深度从小到大访问,因此只要在某层发现第一个左右孩子都为空的节点,就可以立即返回当前深度,不必继续遍历更深层。

这三类题表面问题不同,但真正复用的是“以层为批次处理节点”的结构。遇到题目出现“每层、某一层、最浅、右侧看到”等信号时,应先考虑能否用这一层的固定边界直接产出答案。

常见边界错误

最常见的错误是在 for 循环条件里直接写实时的 queue.size()。因为访问节点时会不断加入孩子,循环上界随之变化,当前层和下一层就会混在一起。

另一个错误是把“节点出队顺序”误当成“层边界”。BFS 确实保证浅层先于深层,但如果题目要求每层单独统计,仍然必须显式记录 levelSize,否则无法可靠知道一层何时结束。

层序遍历的判断要点可以压缩成一句话:进入一层时先冻结队列长度,再用这一批节点计算本层答案。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用层序遍历处理树的分层信息

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通