如何通过递归实现二叉树的按层遍历（指定层级打印节点）

聖光之護 2026-01-20 00:00:00 次阅读

本文详解 `printgivenlevel` 递归函数的工作原理：它从根节点（第1层）开始倒计时式递归，每下探一层将目标层级参数减1，直至为1时打印当前节点——这是理解层级遍历递归本质的关键。

在二叉树的层级遍历中，“按指定层打印节点”看似简单，但其递归逻辑常令人困惑。核心在于：level 参数不是“当前所在深度”，而是“距离目标层还剩几层”——它是一个自顶向下递减的计数器。

以示例树为例：

       50        ← 实际第1层（root）
     /    \
   30      70    ← 实际第2层
  /  \    /  \
20   40  60   80 ← 实际第3层

当调用 printGivenLevel(root, 2) 时，含义是：“请打印实际第2层的所有节点”。函数执行流程如下：

初始调用：printGivenLevel(50, 2)
- root ≠ null，且 level == 2 > 1 → 进入 else if 分支
- 递归调用左子树：printGivenLevel(30, 1)
- 递归调用右子树：printGivenLevel(70, 1)
左子递归：printGivenLevel(30, 1)
- level == 1 → 满足基线条件，直接输出 30
右子递归：printGivenLevel(70, 1)
- 同样 level == 1 → 输出 70

最终输出：30 70 —— 完美对应第2层。

✅ 为什么必须用 level - 1？不能用 level + 1？

因为 level 是

目标层级的剩余步数，而非当前深度。若改为 level + 1：

初始调用 printGivenLevel(root, 2) 会变成 printGivenLevel(left, 3) → printGivenLevel(left, 4) → …无限递增；
永远无法触发 level == 1 的打印条件；
最终导致栈溢出（StackOverflowError），且无任何输出。

? 递归终止的关键：倒计时机制

该算法采用“自顶向下倒计时”策略：

根节点对应 level = n（n为期望层数）；
每深入一层，level 减 1；
当 level == 1 时，说明已精准抵达目标层，执行打印；
若 level

? 补充：完整层级遍历（BFS）的实用写法

虽然本例聚焦单层打印，但可轻松扩展为完整层序遍历：

static void printAllLevels(node root) {
    int h = height(root); // 获取树高
    for (int i = 1; i <= h; i++) {
        System.out.print("Level " + i + ": ");
        printGivenLevel(root, i);
        System.out.println();
    }
}