跳到主要内容

二叉树层次遍历

层次遍历的核心工具是队列 (Queue)，通过 size 控制每一层的处理逻辑。

199. 二叉树的右视图 (Binary Tree Right Side View)​

题目描述​

给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

解题思路​

BFS 队列 + 最后一个节点入结果。

  1. 标准层序遍历。
  2. 每一层遍历到最后一个元素 i == size - 1 时，将其存入 List。

Java 代码实现​

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                if (i == size - 1) res.add(node.val);
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
        }
        return res;
    }
}

637. 二叉树的层平均值 (Average of Levels in Binary Tree)​

题目描述​

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10^-5 以内的答案将被视为正确。

解题思路​

层序遍历累加求均值。 在 while 内部处理每一层时，将 node.val 累计并除以 size。

Java 代码实现​

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            double sum = 0;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                sum += node.val;
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
            res.add(sum / size);
        }
        return res;
    }
}

102. 二叉树的层序遍历 (Binary Tree Level Order Traversal)​

题目描述​

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

解题思路​

BFS 队列控制层级。 标准 while 循环里套 for 循环，每一层创建一个 List 并添加到总的结果集中。

Java 代码实现​

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode n = q.poll();
                level.add(n.val);
                if (n.left != null) q.offer(n.left);
                if (n.right != null) q.offer(n.right);
            }
            res.add(level);
        }
        return res;
    }
}

103. 二叉树的锯齿形层序遍历 (Binary Tree Zigzag Level Order Traversal)​

题目描述​

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，下一层从右往左进行遍历，以此类推，层与层之间交替进行）。

解题思路​

层序遍历 + Deque 头尾插入。 使用 LinkedList 作为这一层的容器。如果当前层是奇数层，使用 list.add(val)，如果是偶数层，使用 list.addFirst(val)。

Java 代码实现​

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        boolean leftToRight = true;
        while (!q.isEmpty()) {
            LinkedList<Integer> level = new LinkedList<>();
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                if (leftToRight) level.addLast(node.val);
                else level.addFirst(node.val);
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
            res.add(level);
            leftToRight = !leftToRight;
        }
        return res;
    }
}