四、树与二叉树（第 31-50 题）｜数据结构 · 笔试 100+7 题

四、树与二叉树（第 31-50 题）

31. 一棵二叉树有n个节点，其叶子节点数为n₀，度为2的节点数为n₂，则( )

标签：【互联网/国企笔试超高频】

A. n₀ = n₂ + 1 B. n₀ = n₂ - 1 C. n₀ = n₂ D. n₀ = 2n₂

答案：A

【结论】 二叉树中 n₀ = n₂ + 1，选 A。

【推导过程】 从两个角度数“边”

① 按结点数:除根外每个结点都有一条来自父结点的边
   边数 = n − 1 = (n₀ + n₁ + n₂) − 1
② 按度:度为 i 的结点向下伸出 i 条边
   边数 = 0×n₀ + 1×n₁ + 2×n₂ = n₁ + 2n₂

两边相等:n₀ + n₁ + n₂ − 1 = n₁ + 2n₂
化简得:n₀ = n₂ + 1

【逐项辨析】

A n₀ = n₂ + 1：正确。 叶子数总比双分支结点数多 1。
B n₀ = n₂ − 1：方向反了，叶子不可能比双分支结点少。
C n₀ = n₂：不是通用性质。
D n₀ = 2n₂：无依据。

【知识点】 二叉树的核心性质（必背）：

性质	公式	说明
结点数与边数	边数 = n − 1	树的基本性质
叶子与双分支	n₀ = n₂ + 1	本题性质
结点总数	n = n₀ + n₁ + n₂	按度分类求和
第 i 层最多	2^(i−1) 个结点	见第 33 题
深度 k 最多	2^k − 1 个结点	见第 34 题

直观理解：每个度为 2 的结点“多生出”一条分支，而所有分支最终都指向叶子，所以叶子总比双分支结点多 1。

【记忆锚点】 “叶子比双分支多一个”——记住“多 1”，方向就不会错。

【易混对比】 注意与“一般树”公式区分：二叉树用 n₀ = n₂ + 1;一般树（度为 m）要用 n₀ = 1 + Σ(i−1)·nᵢ（见第 38 题）。二叉树公式其实是一般树公式在 m = 2 时的特例：1 + (0×n₁ + 1×n₂) = n₂ + 1 ✓。

【自测】 一棵二叉树有 10 个度为 2 的结点，则叶子结点数是多少？

答：11。由 n₀ = n₂ + 1 = 10 + 1 = 11。与第 32 题连考。

【知识关联】

同库连考：与第 36 题（前序+中序还原）、第 37 题（遍历序列）构成遍历专题；与第 42 题（BST 中序有序）、第 38 题（树的度数与结点数）相连。
工程实现：编译器 AST 遍历、文件系统目录树（前序=深度优先进入顺序）、XML 解析；Java 中树的 visitor 模式本质是三次遍历的封装。
408 / 国企真题:408「二叉树遍历」必考；国网真题库原题。
面试追问:①「已知前序和后序能还原二叉树吗？」（不能，缺左右划分）；②「中序+层序呢？」（可以）。

【拓展延伸】

变式:Morris 遍历 O(1) 空间；迭代版遍历用显式栈；层序用队列。

完整对照:

前序:根 → 左 → 右
中序:左 → 根 → 右
后序:左 → 右 → 根
层序:队列 BFS

工程应用：前序适合「先处理根再处理子树」（复制树）；后序适合「先删孩子再删根」（释放）；中序在 BST 上得有序序列。

32. 一棵完全二叉树有100个节点，则该树的叶子节点数为( )

标签：【互联网/国企笔试超高频】

A. 49 B. 52 C. 51 D. 50

答案：D

【结论】 100 个结点的完全二叉树有 50 个叶子结点，选 D。

【推导过程】 完全二叉树中，度为 1 的结点数 n₁ 只能是 0 或 1。联立两个方程

① n₀ + n₁ + n₂ = 100      (结点总数)
② n₀ = n₂ + 1              (二叉树性质)

把 ② 代入 ①:n₂ + 1 + n₁ + n₂ = 100
            2n₂ + n₁ = 99

分类讨论：- 若 n₁ = 1，则 2n₂ = 98 → n₂ = 49,n₀ = 50 ✓（整数解，成立）

若 n₁ = 0，则 2n₂ = 99 → n₂ = 49.5 ✗（非整数，不成立）

故 n₁ = 1,n₂ = 49,n₀ = 50。

【逐项辨析】

A 49：误把 n₂ 当成 n₀，或漏掉 n₁ = 1 这一情况。
D 50：正确。 由上述推导唯一确定。
C 51：把 n₀ = n₂ + 1 中的 n₂ 错算成 50。
B 52：计算错误。

【知识点】 完全二叉树叶子数的快速求法（捷径）：

n 为偶数 → n₁ = 1,n₀ = n/2
n 为奇数 → n₁ = 0,n₀ = (n+1)/2

本题 n = 100(偶数)→ n₀ = 100/2 = 50  ✓

推导依据：n = n₀ + n₁ + n₂ = (n₂+1) + n₁ + n₂ = 2n₂ + n₁ + 1。

n 为偶数 → 2n₂ + n₁ 为奇数 → n₁ = 1 → n = 2n₂ + 2 → n₀ = n₂ + 1 = n/2
n 为奇数 → n₁ = 0 → n = 2n₂ + 1 → n₀ = (n+1)/2

【记忆锚点】 “偶数取一半，奇数加一再取半”——n 偶则 n₀ = n/2;n 奇则 n₀ = (n+1)/2。

【易混对比】 注意完全二叉树“结点总数 n”与“深度”的换算：深度 = ⌊log₂n⌋ + 1（见第 35 题）。本题只求叶子数，不涉及深度。

【自测】 一棵完全二叉树有 101 个结点，叶子结点数是多少？

答：51。n = 101 为奇数，n₀ = (101+1)/2 = 51。与本题对照记忆。

【知识关联】

同库连考：与第 50 题（完全二叉树叶子 n₀ 公式）直接对照 —— 本题用「满的性质」推 n₀=n₂+1 与完全二叉树特化；与第 33~35 题（层结点、深度）同一性质网。
工程实现：堆（大顶/小顶）就是完全二叉树的顺序存储；PriorityQueue 底层是 Object[] 堆；叶子数公式用于算堆最后一层偏移。
408 / 国企真题:408 与国网「二叉树性质计算」高频。
面试追问:①「100 个结点完全二叉树叶子？」（50，见第 50 题）；②「高度为 h 的完全二叉树结点数范围？」（2^{h-1} 到 2^h − 1）。

【拓展延伸】

完整验算:

n=100
n₀ = ⌈n/2⌉ = 50 ✓ (n 偶)
n=101 → n₀ = 51
n=10 → n₀=5
n=7(满) → n₀=4

公式推导：完全二叉树 n₁ ∈ {0,1}；由 n=n₀+n₁+n₂ 与 n₀=n₂+1 联立即得。

变式：求「第 i 个叶子在数组中的下标」需结合层偏移；工程堆的「下沉」操作只在非叶结点上循环。

工程应用：堆化 heapify 从最后一个非叶开始，非叶个数 = ⌊n/2⌋。

33. 一棵二叉树第i层上最多有( )个节点(i ≥ 1)。

标签：【互联网/国企笔试超高频】

A. 2^(i-1) B. 2^i C. 2i - 1 D. 2^(i+1)

答案：A

【结论】 第 i 层最多有 2^(i−1) 个结点，选 A。

【逐项辨析】

B 2^i：多乘了一个 2。
A 2^(i−1)：正确。 每层结点数最多是上一层的 2 倍，第 1 层为 2⁰ = 1。
C 2i − 1：这是等差数列，与二叉树的倍增规律无关。
D 2^(i+1)：指数偏大。

【知识点】 二叉树每层结点数的倍增规律

层号 i	最多结点数	计算
1	1	2⁰
2	2	2¹
3	4	2²
4	8	2³
i	2^(i−1)	—

为什么是 2^(i−1)? 每个结点最多有 2 个孩子，所以下一层结点数最多是上一层的 2 倍。从第 1 层的 1 个结点开始翻倍 i−1 次，即 2^(i−1)。

由此可推：深度为 k 的二叉树最多有 2⁰ + 2¹ + … + 2^(k−1) = 2^k − 1 个结点（即满二叉树，见第 34 题）。

【记忆锚点】 “第 i 层 2^(i−1)，前 k 层 2^k − 1”——层数减一作指数，总层数作指数后减一。

【易混对比】 三个易混公式的区分

问法	公式
第 i 层最多结点数	2^(i−1)
深度为 k 的二叉树最多结点数	2^k − 1
具有 n 个结点的完全二叉树深度	⌊log₂n⌋ + 1

【自测】 一棵二叉树第 5 层最多有多少个结点？

答：2^(5−1) = 2⁴ = 16 个。与第 34 题连考。

【知识关联】

同库连考：与第 34 题（深度 k 满树总结点 2^k−1）、第 35 题（完全二叉树深度 ⌊log₂n⌋+1）、第 50 题（给高度与最后一层求总结点）构成「二叉树数量公式」铁三角；与第 67 题（二分判定树高）同一对数骨架。
工程实现：堆（PriorityQueue）数组下标 1-based 时，结点 i 的孩子是 2i、2i+1，背后就是「每层结点数翻倍」；跳表上层结点近似减半，高度 O(log n)；B+ 树每层扇出更大，高度估算同属「指数展宽 → 层数对数」。
408 / 国企真题：408「二叉树第 i 层最多结点数」原题；国网计算题常变体为「第 k 层最多多少」「前 k 层最多多少」「完全二叉树第 8 层有 20 个则总结点多少」（2^7−1+20=147）。
面试追问:①「第 i 层最多几个？」（2^{i−1}）；②「前 i 层最多几个？」（2^i−1）；③「m 叉树第 i 层？」（m^{i−1}）；④「为什么？」（每个结点最多 m 个孩子，逐层乘 m）。

【拓展延伸】

变式问法:①「第 i 层最多？」（2^{i−1}，本题）；②「深度 k 最多结点？」（2^k−1）；③「n 个结点完全二叉树深度？」（⌊log₂n⌋+1）。

工程映射：内存池二分块、游戏四叉树/八叉树按层展开、Git 提交图的扇出分析、「指数退避」重试策略，都是每层翻倍/乘扇出的同构模型。

易错提醒：i 从 1 开始，指数是 i−1 不是 i；与「前 k 层 2^k−1」不要写反。选项 C「2i−1」是等差干扰，与倍增无关。

34. 深度为k的满二叉树有( )个节点。

标签：【互联网/国企笔试高频】

A. 2^k B. 2^k - 1 C. 2^(k+1) - 1 D. 2^(k-1)

答案：B

【结论】 深度为 k 的满二叉树有 2^k − 1 个结点，选 B。

【推导过程】 满二叉树每层结点数都达到最大值，逐层求和

第 1 层:2⁰ = 1
第 2 层:2¹ = 2
第 3 层:2² = 4
...
第 k 层:2^(k−1)

总数 = 2⁰ + 2¹ + 2² + ... + 2^(k−1) = 2^k − 1   (等比数列求和)

【逐项辨析】

A 2^k：少减了 1。
B 2^k − 1：正确。 等比数列 1 + 2 + 4 + … + 2^(k−1) 的和。
C 2^(k+1) − 1：指数偏大一层。
D 2^(k−1)：这是第 k 层的结点数，不是总数。

【知识点】 满二叉树与完全二叉树的区别（易混）：

	满二叉树	完全二叉树
定义	每层结点数都达到最大	除最后一层外各层满，最后一层结点靠左连续
结点总数	一定是 2^k − 1	不固定，范围 2^(k−1) ~ 2^k − 1
包含关系	一定是完全二叉树	不一定是满二叉树

满二叉树(深度 3,共 7 个):        完全二叉树(深度 3,共 5 个):
        A                                  A
      /   \                              /   \
     B     C                            B     C
    / \   / \                          / \   /
   D   E F   G                        D   E F

【记忆锚点】 “满二叉树：层满人满，总数 2^k − 1；完全二叉树：只差最后一层，还得靠左站”。

【易混对比】 考试中最爱考的陷阱：“完全二叉树”不等于“满二叉树”。完全二叉树允许最后一层不满，但必须从左到右连续排列。第 50 题就是这一区分的典型应用。

【自测】 深度为 5 的满二叉树有多少个结点？

答：2⁵ − 1 = 31 个。与第 50 题（完全二叉树结点数）对照记忆。

【知识关联】

同库连考：与第 33 题（每层最多）、第 35 题（由 n 求深度）、第 50 题（完全二叉树叶子）互为正逆；与第 40 题（哈夫曼树不是完全二叉树）对照。
工程实现：堆的数组长度与高度关系 size = 2^h - 1；线段树开 4n 空间即由满二叉树结点上界而来。
408 / 国企真题:408 与国网计算题。
面试追问:①「完全二叉树与满二叉树区别？」（完全最后一层可不满但必须靠左）；②「深度 10 的满树有多少叶子？」(2^9=512)。

【拓展延伸】

完整验算:

深度 k 满二叉树:2^k - 1
k=5 → 31;k=10 → 1023

变式：完全二叉树 n 个结点，深度 = ⌊log₂n⌋+1（第 35 题）。

工程应用：线段树空间、堆的高度上界 ⌊log₂n⌋、红黑树高度上界 2log₂(n+1)。

35. 具有n个节点的完全二叉树的深度为( )

标签：【互联网/国企笔试高频】

A. ⌊log₂n⌋ B. ⌊log₂n⌋ + 1 C. ⌈log₂(n+1)⌉ D. B和C都对

答案：D

【结论】 两个公式等价，故选 D（B 和 C 都对）。

【逐项辨析】

A ⌊log₂n⌋：漏了 +1，这是把“深度”从 0 开始计数的结果。
B ⌊log₂n⌋ + 1：正确，是深度公式之一。
C ⌈log₂(n+1)⌉：也正确，与 B 等价。
D B 和 C 都对：正确。 因为 ⌊log₂n⌋ + 1 与 ⌈log₂(n+1)⌉ 恒等。

【知识点】 完全二叉树深度公式（两个等价形式）：

深度 = ⌊log₂n⌋ + 1 = ⌈log₂(n+1)⌉

验证

n	⌊log₂n⌋ + 1	⌈log₂(n+1)⌉	是否相等
7	⌊2.807⌋+1 = 3	⌈3⌉ = 3	✓
8	⌊3⌋+1 = 4	⌈3.17⌉ = 4	✓
100	⌊6.64⌋+1 = 7	⌈6.66⌉ = 7	✓

为什么两式等价？ 设深度为 h，则完全二叉树的结点数 n 满足 2^(h−1) ≤ n < 2^h（最少时前 h−1 层满 + 第 h 层 1 个；最多时 h 层全满）。对不等式取对数即得两式。

【记忆锚点】 “深度从 1 起算，所以要 +1”——把 ⌊log₂n⌋ 看成“层数减一”，加 1 才是真正的深度。

【易错提醒】 注意“深度”从 1 开始计数（根结点深度为 1），所以公式中要 +1，不能写成 ⌊log₂n⌋。另注意：整棵树的深度 = 高度，但“某结点的高度”定义为从该结点到叶子结点的最长路径长度。

【易混对比】 与“第 i 层最多 2^(i−1)”（第 33 题）、“深度 k 最多 2^k − 1”（第 34 题）连考。这三条是二叉树“层 / 深度 / 结点数”换算的完整组合。

【自测】 具有 1000 个结点的完全二叉树深度是多少？

答：⌊log₂1000⌋ + 1 = 9 + 1 = 10。验证：2⁹ = 512 ≤ 1000 < 1024 = 2¹⁰，故深度为 10。与第 50 题连考。

【知识关联】

同库连考：与第 33、34 题正逆；与第 67 题（二分比较次数 = 树高）同一 log 来源；与第 32、50 题（叶子数）不同问法。
工程实现:PriorityQueue 的 siftUp 比较次数 ≤ 树高；TreeMap 查询 O(log n) 对应高度。
408 / 国企真题:408 与国网公式题。
面试追问:①「完全二叉树 1000 个结点深度？」(⌊log₂1000⌋+1=10);②「为什么是 +1？」（深度从 1 起算）。

【拓展延伸】

完整验算:

深度 = ⌊log₂n⌋ + 1
n=1 → 1;n=2,3 → 2;n=4..7 → 3;n=8..15 → 4
n=1000:log₂1000≈9.96 → 9+1=10 ✓

变式：结点高度（到叶子最长边数）与深度（到根边数+1）定义要分清；空树深度 0。

工程应用：堆操作 O(log n) 的 n 就是这个深度；解释了为何百万结点的堆也只需约 20 层。

36. 已知一棵二叉树的前序遍历序列为ABDECF，中序遍历序列为DBEACF，则其后序遍历序列为( )

标签：【互联网/国企笔试超高频】

A. DEBFCA B. DBEFCA C. DFEBCA D. DEFCBA

答案：A

【结论】 后序遍历序列为 DEBFCA，选 A。

【推导过程】 前序 ABDECF、中序 DBEACF，逐步还原二叉树

第 1 步:前序第一个 A 是根
第 2 步:中序中 A 把序列分为 DBE(左子树) 和 CF(右子树)
第 3 步:左子树 前序 BDE、中序 DBE → B 为根,D 为左孩子,E 为右孩子
第 4 步:右子树 前序 CF、中序 CF → C 为根,F 为右孩子

还原出的树

          A
        /   \
       B     C
      / \     \
     D   E     F

后序遍历（左 → 右 → 根）：D → E → B → F → C → A = DEBFCA。

【逐项辨析】

A DEBFCA：正确。 按还原后的树做后序遍历。
B DBEFCA：左子树内部顺序错（D、E 颠倒）。
C DFEBCA：右子树 F 的位置错。
D DEFCBA：根 A 的位置虽对，但子树顺序错乱。

【知识点】 由两种遍历序列还原二叉树的规则

已知序列组合	能否唯一确定	依据
前序 + 中序	✅ 能	前序定根，中序分左右
后序 + 中序	✅ 能	后序定根，中序分左右
前序 + 后序	❌ 不能	无法区分只有一个孩子时该孩子在哪侧
层序 + 中序	✅ 能	层序定根

通用方法（递归）：

由前序（或后序）确定根;
在中序中定位根，根左边是左子树、右边是右子树;
按左右子树的结点数，在前序 / 后序中切分出对应的子序列；4. 对左右子树递归重复上述步骤。

【记忆锚点】 “前序后序定根，中序分左右”——必须配上中序才能分左右，所以前序 + 后序不行。

【易混对比】 三种遍历的顺序

遍历	顺序	记忆
前序	根 → 左 → 右	根在最前
中序	左 → 根 → 右	根在中间
后序	左 → 右 → 根	根在最后

【自测】 已知前序 ABC、后序 CBA，能唯一确定这棵二叉树吗？

答：不能。 根为 A，但 B、C 谁是左孩子谁是右孩子无法确定，可能是 A-B-C（左链），也可能是 A-C-B（右链）。这正是“前序 + 后序不唯一”的经典反例。

【知识关联】

同库连考：与第 37 题（由前中求后序）互为逆运算；与第 31 题（n₀=n₂+1 的度数守恒）同属二叉树计数基础；与第 42 题（BST 中序有序）应用。
工程实现：编译器语法树重建、XML/JSON 从遍历序列恢复结构、生物信息学中的系统发生树重建。
408 / 国企真题:408 操作题必考；国网「树」模块高频。
面试追问:①「前序+后序为何不行？」（无法确定单孩子时左右）；②「中序+层序可以吗？」（可以）。

【拓展延伸】

完整验算方法:

前序 ABDECF 根=A
中序 DBEACF → 左 DBE,右 CF
递归:左子树前序 BDE 中序 DBE → 根 B,左 D,右 E
右子树前序 CF 中序 CF → 根 C,右 F

变式：画出树后立刻可写后序/层序；有重复元素时前中后组合可能不唯一。

工程应用：序列化二叉树（前序+空标记）与反序列化是 LeetCode 297。

37. 已知一棵二叉树的后序遍历序列为DEBFCA，中序遍历序列为DBEACF，则其前序遍历序列为( )

标签：【互联网/国企笔试高频】

A. ABDECF B. ABCDEF C. ADBECF D. ABDCFE

答案：A

【知识点】 由两种遍历还原二叉树的规则与后序书写：1. 前序/后序定根，中序分左右 —— 前序首元素或后序末元素是根；用根在中序中切开左/右子树。 2. 前序+后序不能唯一确定二叉树（存在单孩子时左右可翻转）。 3. 本题与第 36 题互为逆运算:36 由前+中画树写后序；本题由后+中画树写前序（与下方【知识点】的两行对照一致）。

书写口诀：「后序尾巴是根，中序切开分左右」。递归切分直到子树为空。若两序列长度不一致或中序中找不到根元素，则序列非法（不对应同一棵树）。

【推导过程】 后序 DEBFCA、中序 DBEACF:

第 1 步:后序最后一个 A 是根
第 2 步:中序中 A 把序列分为 DBE(左) 和 CF(右)
第 3 步:左子树 后序 DEB、中序 DBE → B 为根(后序最后一个),左 D 右 E
第 4 步:右子树 后序 FC、中序 CF → C 为根,右 F

还原出的树（与第 36 题同一棵）：

          A
        /   \
       B     C
      / \     \
     D   E     F

前序遍历（根 → 左 → 右）：A → B → D → E → C → F = ABDECF。

【逐项辨析】

A ABDECF：正确。 按还原后的树做前序遍历。
B ABCDEF：这是层序结果，不是前序。
C ADBECF：左子树内部顺序错。
D ABDCFE：错在左右子树边界——把左子树剩下的 E 排到了右子树 C、F 之后；右子树内部 C→F 的次序本身是对的。

【知识点】 本题与第 36 题互为逆运算:

第 36 题:前序 + 中序 → 求后序
第 37 题:后序 + 中序 → 求前序

核心工具完全相同：后序的最后一个元素 = 前序的第一个元素 = 整棵树的根。

一个实用检验技巧：前序序列的第一个元素与后序序列的最后一个元素必须相同（都是根），且两序列长度相等。用这一条可快速排除部分选项。

【记忆锚点】 “后序尾巴是根，中序切开分左右”。

【易混对比】 注意“前序 + 中序”与“后序 + 中序”都能唯一确定二叉树，但“前序 + 后序”不能。本题与第 36 题连考，是 408 与国网笔试“树”模块的必考操作题。

【自测】 若一棵二叉树的前序为 ABDECF，则其后序的最后一个元素一定是什么？

答：A。前序的第一个元素与后序的最后一个元素都是根结点。与第 36 题连考。

【知识关联】

同库连考：与第 36 题互逆；与第 31 题（n₀=n₂+1）、第 38 题（一般树的度数）同属二叉树计数基础。
工程实现：同第 36 题；验证时可同时写出层序对照。
408 / 国企真题:408 与国网操作题。
面试追问:①「后序最后一个是什么？」（根）；②「中序第一个？」（最左结点）。

【拓展延伸】

完整验算:

第 36 题还原的树:
        A
       / \
      B   C
     / \   \
    D   E   F
后序:左子树 DBE,右子树 F,根 A → DEBFCA

变式：若改为层序 AB…，需结合中序重画。

工程应用：文件系统「先删目录内容再删目录」= 后序；表达式树求值用后序。

38. 一棵度为 4 的树 T 中，度为 1、2、3、4 的结点个数分别为 4、2、1、1，则 T 中叶子结点的个数为( )

标签：【国企笔试超高频】

A. 5 B. 6 C. 7 D. 8

答案：D

【结论】 叶子结点数为 8，选 D。

【推导过程】 从两个角度数“边”

① 按结点数:除根外每个结点都有一条来自父结点的边
   边数 = 结点总数 − 1 = (n₀ + 4 + 2 + 1 + 1) − 1 = n₀ + 7
② 按度:度为 i 的结点向下伸出 i 条边
   边数 = Σ i·nᵢ = 1×4 + 2×2 + 3×1 + 4×1 = 15

两边相等:n₀ + 7 = 15  →  n₀ = 8

【逐项辨析】

A 5 / B 6 / C 7：均为计算过程中的中间数或漏算某一类结点。
D 8：正确。 由“边数两种数法相等”唯一确定。

【知识点】 一般树叶子数的通用公式（必背）：

n₀ = 1 + Σ(i−1)·nᵢ        (i 从 1 取到树的最大度)

本题:n₀ = 1 + (0×4 + 1×2 + 2×1 + 3×1) = 1 + 7 = 8

公式推导： 由 n = Σnᵢ 且边数 = n − 1 = Σ i·nᵢ，代入整理即得。

二叉树公式是一般树公式的特例:

树的类型	叶子数公式	说明
一般树（度为 m）	n₀ = 1 + Σ(i−1)·nᵢ	各度结点都要统计
二叉树	n₀ = n₂ + 1	m = 2 时：1 + (0×n₁ + 1×n₂) = n₂ + 1 ✓

【记忆锚点】 “叶子的度是 0，却要多算一个 1”——公式开头那个 1 来自“根结点没有父边”。

【易错提醒】 ①二叉树用 n₀ = n₂ + 1,一般树必须用 n₀ = 1 + Σ(i−1)·nᵢ，两者不可混用；②统计时度为 1 的结点贡献 0（系数 i−1 = 0），容易漏看；③验算方法：算出 n₀ 后回代，检查“边数 = 结点总数 − 1”是否成立。这是国企笔试（国网 / 运营商）出现频率很高的计算题。

【自测】 一棵度为 3 的树中，度为 1、2、3 的结点数分别为 3、1、2，则叶子结点数为？

答：n₀ = 1 + (0×3 + 1×1 + 2×2) = 6。验算：结点总数 = 6+3+1+2 = 12，边数 = 11 = 3×1 + 2×1 + 3×2 ✓。国网真题库同型题。

【知识关联】

同库连考：与第 32 题（二叉树 n₀=n₂+1）必须对照 —— 二叉树公式是一般树公式在 m=2 时的特例；与第 40 题（哈夫曼树）、第 33~35 题（二叉树数量）同属「树的计数」。
工程实现：文件系统目录树、组织架构树、DOM 树都是一般树；求「无子目录的目录数」可用同一公式。
408 / 国企真题：国网真题库高频计算题；408 考一般树较少但公式要会。
面试追问:①「度为 1 的结点在公式里贡献多少？」（0，因为系数 i−1=0）；②「如何快速验算？」（边数 = 结点总数 − 1 = Σ i·nᵢ）。

【拓展延伸】

完整验算（本题 n₁=4, n₂=2, n₃=1, n₄=1）：

边数(按度)= 1×4 + 2×2 + 3×1 + 4×1 = 4+4+3+4 = 15
边数(按结点)= n−1 = (n₀+4+2+1+1)−1 = n₀+7
n₀+7 = 15 → n₀ = 8 ✓

公式法:n₀ = 1 + (0×4 + 1×2 + 2×1 + 3×1) = 1+7 = 8 ✓

变式:

度为 3 的树，n₁=3,n₂=1,n₃=2 → n₀ = 1+(0+1+4)=6，边数 3+2+6=11，结点 6+3+1+2=12,12−1=11 ✓。
若误用二叉树公式 n₀=n₂+1 会得到 2+1=3（错）。
m 叉树通用式不变，只改变求和上界。

工程应用：文件系统 find -type f 与目录叶子统计、DOM querySelectorAll('*') 后按 children 长度分类计数。

39. 关于红黑树，下列说法正确的是( )

标签：【互联网笔试·Java 高频】

A. 红黑树的查找时间复杂度最坏为 O(n) B. 红黑树通过节点颜色约束（根为黑、红节点的子必黑）保证最长路径不超过最短路径的 2 倍，插入、删除、查找均为 O(log n) C. 红黑树要求任意节点的左右子树高度差不超过 1 D. 红黑树只支持查找，不支持插入和删除

答案：B【结论】 红黑树通过颜色约束保证最长路径不超过最短路径的 2 倍，各操作均为 O(log n)，选 B。

【逐项辨析】

A 错：红黑树查找最坏为 O(log n)，不是 O(n)。（会退化成链的是普通 BST，不是红黑树。）
B 对：根为黑、红结点的子必黑等颜色约束，使最长路径不超过最短路径的 2 倍，插入 / 删除 / 查找均为 O(log n)。
C 错：左右子树高度差不超过 1 是 AVL 树的要求，红黑树没有这条约束。
D 错：红黑树支持插入和删除（并会通过旋转 + 变色恢复性质）。

【知识点】 红黑树的五条性质（必背）：

1. 每个结点是红色或黑色
2. 根结点是黑色
3. 每个叶子结点(NIL 空结点)是黑色
4. 红结点的两个子结点都是黑色(不能出现连续两个红结点)
5. 从任一结点到其所有后代叶子的路径上,黑结点数目相同(黑高相等)

由性质 4、5 可推出核心结论：最长路径 ≤ 2 × 最短路径 —— 最长路径是“红黑交替”，最短路径是全黑，故红黑树是“弱平衡”的。

红黑树 vs AVL 树

	红黑树	AVL 树
平衡标准	最长路径 ≤ 2 × 最短路径	左右子树高度差 ≤ 1
平衡程度	弱平衡	严格平衡
查找效率	略低（树略高）	略高（树更矮）
插入 / 删除旋转	少（≤ 3 次）	多（可能 O(log n) 次）
适用场景	频繁插入删除	查询为主

【记忆锚点】 “红黑树不追求完美平衡，只保证不歪到 2 倍”——用少量旋转换取插入删除的高效。

【易混对比】 三种“树”务必分清

树	关键特征	Java / 系统中的应用
二叉排序树 BST	左 < 根 < 右，可能退化成链	—
AVL 树	严格平衡（高度差 ≤ 1）	—
红黑树	弱平衡（最长 ≤ 2 × 最短）	TreeMap、TreeSet、HashMap 树化

Java 的 TreeMap、TreeSet 及 HashMap（同一桶链长超过 8 才树化，实测见下）底层均为红黑树，互联网笔试超高频。

【自测】 为什么 Java 的 HashMap 用红黑树而不是 AVL 树优化长链表？

答：因为 HashMap 的树化桶插入删除频繁，红黑树旋转次数少、维护成本低；AVL 树虽然查找更快，但每次插入删除都可能触发 O(log n) 次旋转，综合性能不如红黑树。与第 73、78 题连考。

【知识关联】

同库连考：与第 45 题（AVL 严格平衡）对照 —— 弱平衡 vs 严格平衡；与第 73 题（HashMap 树化）、第 78 题（容量 2 的幂）同属 HashMap 工程链；与第 69 题（BST 查找最坏 O(n)）同源 —— 退化都靠平衡结构解决。
工程实现:Java TreeMap/TreeSet 红黑树；HashMap 同一桶结点数超过 8（实测第 9 个）且 table.length ≥ 64 时树化为红黑树；Linux 调度器 CFS、epoll 红黑树定时器。
408 / 国企真题：国企 Java 笔试常考；408 学术上考 AVL 更多，红黑树属进阶。
面试追问:①「为何 HashMap 用红黑不用 AVL？」（插删旋转少，查询略慢可接受）；②「红黑树如何保证 log n？」（最长路径≤2×最短 → 高度 O(log n))。

【拓展延伸】

五条性质回扣：根黑、红结点孩子黑、任一路径黑高相同、叶子(NIL)黑、无连续红。

变式:B 树/B+ 树用于磁盘索引（第 72 题）；跳表(ConcurrentSkipListMap)可替代红黑树提供并发。

工程应用：定时器管理、内存分配器空闲块树、Java 集合排序容器。

40. 哈夫曼树（最优二叉树）的带权路径长度(WPL)最小，它不具有以下哪个特点？

标签：【互联网/国企笔试高频】

A. 没有度为1的节点 B. 权值越大的叶子离根越近 C. 是一棵完全二叉树 D. n个叶子节点的哈夫曼树共有2n-1个节点

答案：C

【结论】 哈夫曼树不一定是完全二叉树，「是一棵完全二叉树」不是它的固有特点，选 C。

【逐项辨析】

A 对：哈夫曼树没有度为 1 的结点 —— 每次合并都把两个结点作为新结点的孩子，新结点度为 2，叶子度为 0。
B 对：权值大的叶子离根近（贪心策略：先合并小权值，后合并大权值）。
C 错：哈夫曼树一般不是完全二叉树。 完全二叉树要求最后一层结点靠左连续，哈夫曼树没有这一约束。（例外要心里有数：四个叶子权值全相等时构造出来恰好是满二叉树，所以严谨表述是「不一定是」，本题考的是「不作为固有特点」。）
D 对：n 个叶子的哈夫曼树共有 2n − 1 个结点（每次合并新增 1 个内部结点，共合并 n−1 次：n + (n−1) = 2n − 1)。

【知识点】 哈夫曼树的四条性质（必背）：

1. 带权路径长度 WPL 最短(这是"最优二叉树"的定义)
2. 没有度为 1 的结点(只有度 0 的叶子和度 2 的内部结点)
3. n 个叶子结点 → 共 2n − 1 个结点
4. 权值越大的叶子离根越近

由性质 2 可得：n₁ = 0,n₀ = n₂ + 1；又 n₀ = n，故 n₂ = n − 1，结点总数 = n₀ + n₂ = 2n − 1 ✓。

反例：哈夫曼树不必是完全二叉树。

权值 {1, 2, 3, 4} 的哈夫曼树:
       10
      /  \
     6    4
    / \
   3   3
  / \
 1   2

共 7 个结点。若为完全二叉树,深度 3 的完全二叉树在 7 个结点时应是满二叉树(第 3 层 4 个结点),
但此树第 3 层仅 2 个结点且右侧子树为空——不满足"最后一层靠左连续",因此不是完全二叉树。

【记忆锚点】 “哈夫曼：无单分支、共 2n−1 个、权大靠上”——三条性质一次记全。

【易混对比】 “最优二叉树”是哈夫曼树的别名，指 WPL 最小的二叉树，不要与“完全二叉树”“满二叉树”混淆。另外注意：哈夫曼树不唯一 —— 当存在相同权值时，不同的合并选择会得到结构不同但 WPL 相同的多棵哈夫曼树。

【自测】 有 8 个叶子的哈夫曼树共有多少个结点？

答：2 × 8 − 1 = 15 个。与第 48 题（WPL 计算）连考。

【知识关联】

同库连考：与第 41 题（性质）、第 48 题（WPL 计算）构成哈夫曼三连；与第 33~34 题（满/完全二叉树）对照 —— 哈夫曼一般不是完全二叉树。
工程实现:Huffman 压缩（zip/gzip/JPEG 熵编码）、霍夫曼编码前缀性、IP 路由前缀树；- 408 / 国企真题:408 与国网「树」模块高频；反例题是进阶考法。
面试追问:①「权值 1,2,3,4 的哈夫曼树是完全二叉树吗？」（可构造出不是）；②「权值全相等时？」（可得到完全形态，但仍不必然）。

【拓展延伸】

完整验算:

权 1,2,3,4:
合并 1+2=3 → 结点3(叶1,叶2)
现有 3,3,4 → 合并 3+3=6
现有 4,6 → 合并 4+6=10
树高不均，非完全二叉树

变式：证明「哈夫曼树无度为 1 结点」；n 个叶子 → 2n−1 个结点。

工程应用:HTTP/2 HPACK、protobuf 字段编码的变长整数也是前缀码思想。

41. 对于n个字符构成的文本，使用哈夫曼编码后，总编码长度最短是因为( )

标签：【互联网/国企笔试常考】

A. 每个字符编码长度相同 B. 使用了固定长度编码 C. 所有编码长度都为log₂n D. 频率高的字符编码短，频率低的编码长

答案：D

【结论】 哈夫曼编码让频率高的字符编码短、频率低的编码长，故总编码长度最短，选 D。

【逐项辨析】

A错：哈夫曼编码是变长编码，各字符编码长度不同。等长编码才“每个字符长度相同”。
D 对：频率高的字符获得较短的编码，频率低的字符获得较长的编码 —— 这正是总长度最短的原因。
C错：只有所有字符等概率时，各编码长度才接近 log₂n；哈夫曼编码并不要求。
B错：固定长度编码正是哈夫曼编码要改进的对象（如 ASCII 用 8 位编码所有字符）。

【知识点】 哈夫曼编码的构造与原理

1. 统计各字符出现的频率(作为权值)
2. 用这些权值构造哈夫曼树
3. 从根出发,向左走记 0、向右走记 1
4. 到达叶子结点的路径即为该字符的编码

为什么总长度最短？ 编码长度 = 叶子深度，加权总长度 = Σ（频率 × 深度） = WPL。而哈夫曼树的 WPL 最小，故总编码长度最短。

字符频率:  a:5   b:2   c:1   d:3
哈夫曼编码后深度:a 深度 1、d 深度 2、b 深度 3、c 深度 3
加权总长度 = 5×1 + 3×2 + 2×3 + 1×3 = 20
若用等长编码(2 位):(5+2+1+3)×2 = 22  → 哈夫曼更短

【记忆锚点】 “频率高的短码，频率低的长码”——把“话多的人”的编码压短，总长度自然最小。

【易混对比】 前缀编码 vs 非前缀编码：哈夫曼编码是前缀编码（任一编码都不是另一编码的前缀），因此解码时不会产生歧义。例如 {0, 10, 11} 是前缀编码；{0, 01, 1} 不是（0 是 01 的前缀，遇到 01 无法判断是“0 后跟 1”还是“01”）。哈夫曼树中字符只出现在叶子结点，这一构造天然保证了前缀性质。

【自测】 为什么哈夫曼编码必须满足“前缀编码”的要求？

答：因为解码时是从左到右逐位匹配，若某个编码是另一个的前缀就会出现歧义（无法确定该读几位）。哈夫曼编码把字符放在叶子结点，天然满足前缀性质。与第 48 题连考。

【知识关联】

同库连考：与第 40 题（非完全二叉树）、第 48 题(WPL=33)同一专题；与第 47 题（TopK 小顶堆）都是「堆/Huffman」思维。
工程实现:gzip/zip 的 Huffman 表、JPEG AC 系数编码；构造用最小堆 O(n log n)。
408 / 国企真题:408 与国网必考性质。
面试追问:①「n 个叶子多少结点？」(2n−1);②「WPL 等于所有非叶结点权值之和」（对吗？对，合并过程累加）。

【拓展延伸】

完整验算:

n 个叶子
每次合并减少 1 个结点(两叶成一父),共 n-1 次合并
总结点 = n + (n-1) = 2n-1
度为 1 结点 = 0
权值越大深度越小(WPL 最小化)

变式：哈夫曼树不唯一（相同权值时）；但 WPL 唯一。

工程应用：最优前缀码、决策树代价最小化、竞赛中的「合并果子」题。

42. 下列关于二叉搜索树(BST)判断方法的说法，正确的是( )

标签：【互联网面试高频】

A. 只需比较每个节点与其左右直接孩子的大小关系即可确定 B. 中序遍历的结果为严格递增序列，是二叉搜索树的充要条件 C. 前序遍历的结果为严格递增序列，是二叉搜索树的充要条件 D. 层序遍历的结果为严格递增序列，是二叉搜索树的充要条件

答案：B【结论】 中序遍历结果为严格递增序列，是 BST 的充要条件，选 B。

【逐项辨析】

A 错：只比较结点与直接孩子不够。反例：根为 10，右孩子为 15，而 15 的左子树中存在 8 —— 8 < 10 却出现在右子树中，该树不是 BST，但「结点与直接孩子」的局部检查（10 < 15、8 < 15）每一对都通过，正因如此才说明「只查父子关系」漏判。
B 对：中序遍历严格递增 ⟺ 二叉搜索树。
C 错：前序递增不构成充要条件（前序是“根左右”，无法反映左右子树的大小关系）。
D 错：层序递增不构成充要条件。

【知识点】 BST 的两个等价判定方法

方法 1(中序法):中序遍历,检查序列是否严格递增
方法 2(上下界法):递归传递区间 (low, high)
  对结点 p,要求 low < p->val < high
  递归左子树时 high = p->val;递归右子树时 low = p->val

两种方法都是 O(n)，但方法 2 更安全 —— 方法 1 需要额外 O(n) 空间存遍历序列（或用 O(1) 的“上一个访问值”做比较）。

反例(为什么只比较父子不够):
          10
         /  \
        5    15
            /
           8      ← 8 < 10,违反 BST 性质
                     但 15 与 8 是父子关系(8 < 15 成立),单看父子会漏判

【记忆锚点】 “中序递增就是 BST”——一句话判定，最省事。

【易混对比】 注意“严格递增”这一措辞：若树中存在相等元素，中序会出现相等值，此时不满足“严格递增”。大多数笔试题默认 BST 中关键字互不相同。

【自测】 用“递归传递上下界”的方法判断一棵树是否为 BST，时间复杂度是多少？

答：O(n)。每个结点只访问一次。大厂技术面试高频考点，常要求手写实现。

【知识关联】

同库连考：与第 44 题（BST 中序有序）本质同一；与第 46 题（删除）、第 69 题（最坏 O(n))、第 70 题（AVL 最坏仍是 O(log n)，见第 43 题「平均 O(log n)」的另一半对照）构成 BST 网；与第 36 题（中序）应用。
工程实现:Java TreeMap 中序遍历 key 有序；数据库索引中序扫描范围查询。
408 / 国企真题:408 与国网 BST 判定。
面试追问:①「只检查根大于左小于右够吗？」（不够，要递归上下界）；②「有重复元素？」（需约定放左或右）。

【拓展延伸】

完整验算：中序得严格递增序列 ⇔ BST。验证算法 O(n)。

变式：用「递归传递 min/max」或「迭代中序比较前驱」实现。

工程应用：范围查询 subMap、有序遍历导出、区间树。

43. 二叉排序树(BST)中，查找操作的平均时间复杂度为( )

标签：【互联网/国企笔试高频】

A. O(1) B. O(log n) C. O(n) D. O(n log n)

答案：B

【结论】 平均时间复杂度为 O(log n)，选 B。

【逐项辨析】

A O(1)：这是哈希表查找的平均复杂度，不是 BST。
B O(log n)：正确。 对随机插入构造的 BST，期望高度为 O(log n)。
C O(n)：这是 BST 最坏情况的复杂度（退化成链），不是平均。
D O(n log n)：这是排序的量级，不是单次查找。

【知识点】 BST 查找的复杂度取决于树的高度 h:

情况	树的高度	查找复杂度	原因
平均（随机插入）	O(log n)	O(log n)	树大致平衡
最好（完全平衡）	⌊log₂n⌋+1	O(log n)	类似折半查找
最坏（有序插入）	n	O(n)	退化成单链

有序插入 1, 2, 3, 4, 5 得到的 BST(退化成链):
1
 \
  2
   \
    3
     \
      4
       \
        5

【记忆锚点】 “随机插树矮，顺序插树高”——BST 的效率取决于插入顺序。

【易混对比】 与第 69 题（最坏 O(n))对照记忆：题目问“平均”选 O(log n)，问“最坏”选 O(n)。为避免退化，可使用 AVL 树或红黑树等自平衡二叉搜索树（见第 39、45 题）。

【自测】 依次插入 1、2、3、4、5 构造 BST，查找 5 需要比较几次？

答：5 次。树退化成单链，必须从头走到尾。与第 69 题连考。

【知识关联】

同库连考：与第 69 题（BST 最坏 O(n)）必成对——平均选 log n，最坏选 n；与第 70 题（AVL 最坏仍是 log n）、第 45 题（AVL 定义）、第 39 题（红黑树）构成「BST 与平衡树」链；与第 65/76 题（二分）对照：平衡 BST 查找与二分同阶，但 BST 支持动态插入删除。
工程实现：裸 BST 在随机数据下期望高 ~2 ln n；生产环境用 TreeMap（红黑树）、数据库用 B+ 树，避免有序输入退化；HashMap 树化也是为了冲突链过长时把查找从 O(n) 拉回 O(log n)。
408 / 国企真题：408「二叉排序树平均查找长度/时间复杂度」标准答案 O(log n)（随机插入假设）；真题常同时问最坏，务必看「平均/最坏」字样。国网计算题会给定关键字序列画 BST 再数比较次数。
面试追问:①「平均为何是 log n？」（随机插入下树高期望 O(log n)）；②「有序插入呢？」（退化单链，O(n)，见第 69 题）；③「ASL 与树高关系？」（成功查找平均比较次数与平均深度同阶）。

【拓展延伸】

变式问法:①「BST 查找平均？」（O(log n)，本题）；②「最坏？」（O(n)）；③「平衡 BST 最坏？」（仍 O(log n)）。

工程映射：解释「为何内存有序映射用红黑树/跳表、磁盘用 B+ 树，而不是裸 BST」；面试手写 BST 后必追问有序输入退化，本题是平均口径的锚点。

易错提醒：平均 O(log n) 建立在随机插入/随机数据假设上，不是无条件成立；题干若写「一定为 O(log n)」则是错的（那是第 74 题 C 选项的陷阱）。

44. 在二叉排序树中，( )的遍历结果是有序序列。

标签：【互联网/国企笔试高频】

A. 前序遍历 B. 中序遍历 C. 后序遍历 D. 层序遍历

答案：B

【知识点】 BST 的定义与中序有序性的证明思路：BST：左子树所有结点关键字 < 根 < 右子树所有结点关键字（递归定义）。

中序遍历序列严格递增 ⇔ 该二叉树是 BST（在关键字互不相同的前提下）。

证明方向：①是 BST ⇒ 中序时「访问左（全小）→ 根 → 右（全大）」自然递增；②中序递增 ⇒ 任意子树的根必在左段与右段之间，满足 BST 定义。

验证算法：中序扫描，维护前驱值，若当前 ≤ 前驱则非法，O(n) 时间 O(h) 空间。注意「严格递增」措辞：若允许重复，需规定重复放左或右，此时中序为非降序。

【逐项辨析】

A 前序遍历：顺序是“根 → 左 → 右”，先访问根，不可能有序。
B 中序遍历：正确。 顺序是“左 → 根 → 右”，恰好从小到大。
C 后序遍历：顺序是“左 → 右 → 根”，根最后访问，不可能有序。
D 层序遍历：按层访问，与大小顺序无关。

【知识点】 BST 的定义与中序有序性的证明

BST 定义:对任一结点,左子树所有值 < 根值 < 右子树所有值

中序遍历:左子树 → 根 → 右子树
  左子树所有值 < 根值(定义)
  根值 < 右子树所有值(定义)
  → 遍历序列从小到大 → 有序 ✓

这是 BST 最重要的性质，也是“判断一棵树是否为 BST”的标准方法（见第 42 题）。

【记忆锚点】 “BST 中序走一遍，从小到大排成串”。

【易混对比】 遍历方式与用途对照

遍历	典型用途
中序	BST 得到有序序列；表达式树得到中缀表达式
前序	复制 / 序列化一棵树
后序	释放树的空间；计算表达式树的值
层序	求树宽、按层打印

【自测】 对一棵 BST 做中序遍历得到 3, 7, 9, 12, 20，则该树中最小的元素是什么？

答：3。中序第一个元素即最小值（最左下的结点）。与第 46 题（BST 删除）连考。

【知识关联】

同库连考：与第 42 题（验证 BST）同一判据；与第 69、70 题（BST 最坏 vs AVL）构成「平衡与否决定最坏」对照。
工程实现：有序导出、TreeMap.values() 顺序、数据库索引中序扫描。
408 / 国企真题:408 与国网。
面试追问:①「如何 O(n) 验证？」（中序比前驱）；②「BST 的前序有什么特征？」（可用于建树）。

【拓展延伸】

变式：中序第一个=最小，最后一个=最大；中序后继/前驱用于迭代器。

工程应用：有序合并、范围删除、rank/select 操作。

完整验算：对树做中序，若任意相邻 u < v 成立则有序。

45. 平衡二叉树（AVL树）的任意节点的左右子树高度差的绝对值不超过( )

标签：【互联网/国企笔试常考】

A. 0 B. 3 C. 2 D. 1

答案：D

【结论】 平衡因子的绝对值不超过 1，选 D。

【逐项辨析】

A 0：要求左右子树高度完全相同，过于严格（只有完美满二叉树才满足），不是 AVL 的定义。
D 1：正确。 AVL 树要求任一结点的平衡因子 ∈ {−1, 0, +1}。
C 2 / B 3：过于宽松，达不到 AVL 树的严格平衡要求。

【知识点】 AVL 树的定义与失衡处理

平衡因子 BF = 左子树高度 − 右子树高度
AVL 树要求:对任一结点,|BF| ≤ 1

插入 / 删除导致 |BF| = 2 时，需要旋转恢复平衡 —— 四种旋转:

失衡类型	失衡原因	恢复方法
LL 型	在左子树的左子树插入	右旋
RR 型	在右子树的右子树插入	左旋
LR 型	在左子树的右子树插入	先左旋再右旋
RL 型	在右子树的左子树插入	先右旋再左旋

AVL 树保证树高恒为 O(log n)，故查找、插入、删除均为 O(log n)。

【记忆锚点】 “AVL 树，高度差不过一”——记住“1”这个数字。

【易混对比】 与红黑树对照（见第 39 题）：AVL 是严格平衡（高度差 ≤ 1），红黑树是弱平衡（最长 ≤ 2 × 最短）。AVL 查找更快但插删旋转多；红黑树插删代价小，更适合频繁修改的场景。

【自测】 一棵 AVL 树在插入一个结点后，某结点的平衡因子变成了 +2，说明什么？

答：说明左子树比右子树高 2，树已失衡，需要通过旋转（LL 型右旋、LR 型先左旋再右旋）恢复平衡。408 与国网笔试高频考点。

【知识关联】

同库连考：与第 39 题（红黑树弱平衡）对照：AVL |高度差|≤1，红黑最长≤2×最短；与第 43/69/70 题（BST 平均/最坏/AVL 复杂度）相连——本题是「为何 AVL 查找能保证 O(log n)」的定义前提；与第 46 题（BST 删除）后平衡维护对照。
工程实现：Java TreeMap/TreeSet、C++ std::map 用红黑树不用 AVL——插删旋转更少，适合写多场景；Linux 调度器 CFS、内存管理曾用红黑树；教学与部分内存数据库在读多场景仍可用 AVL。面试说「平衡树」要能对比 AVL vs 红黑的取舍。
408 / 国企真题：408「AVL 树任一结点平衡因子」标准答案绝对值不超过 1；旋转题（LL/RR/LR/RL）是 408 大题高频；国企选择题常考定义数字「1」，以及插入后 BF=±2 表示失衡。
面试追问:①「BF=+2 什么意思？」（左子树高 2，失衡，需旋转）；②「插入最多旋转几次？」（1~2 次，且自底向上一次即可恢复）；③「删除为何可能多次旋转？」（失衡可能向上传播）；④「为何工程偏红黑？」（平衡更松，插删更省）。

【拓展延伸】

变式问法:①「AVL 高度差不超过？」（1，本题）；②「四种旋转分别对应？」（LL 右旋、RR 左旋、LR 先左后右、RL 先右后左）；③「高度 h 的 AVL 最少结点？」（递推 N(h)=N(h−1)+N(h−2)+1，斐波那契式增长）。

工程映射：有序字典、任务优先级索引、需要最坏可控查找的内存结构；对比「跳表（Redis zset）」用随机层高换平衡，是 AVL 思想的工程变体。

易错提醒：平衡因子 = 左高 − 右高，约定左右方向别反；A 选项「0」是完美平衡，不是 AVL 定义。红黑树不要求高度差≤1，勿混。

46. 在二叉排序树中删除一个结点，下列说法正确的是( )

标签：【国企笔试高频】

A. 删除叶子结点后，需要重新调整整棵树的平衡 B. 删除度为 1 的结点时，必须先删除其孩子，再删除该结点 C. 删除度为 2 的结点时，可用其左子树中的最大结点（中序前驱）或右子树中的最小结点（中序后继）替代，再删除被替代的结点 D. 二叉排序树删除结点后一定不再保持有序性

答案：C

【结论】 删除度为 2 的结点时，用中序前驱或中序后继替代，再删除被替代的结点，选 C。

【逐项辨析】

A 错：普通 BST 不要求平衡，删除叶子只做局部指针调整（把父结点对应指针置空）；只有 AVL 树、红黑树删除后才需要旋转恢复平衡。
B 错：度为 1 时应让孩子直接顶替它的位置，而不是先删孩子。
C 对：先用中序前驱（左子树中最大）或中序后继（右子树中最小）的关键字替换它，再按叶子 / 单分支的方式删除那个前驱 / 后继结点。
D 错：按三种情况处理后可完整保持 BST 的中序有序性。

【知识点】 BST 删除的三种情况（按结点度分类，必背）：

待删结点	处理方法	示意
叶子结点（度 0）	直接删除，把父结点相应指针置空	`p->left = NULL`
度为 1	用其唯一的孩子顶替它的位置	孩子直接挂到父结点上
度为 2	用中序前驱（左子树最大）或中序后继（右子树最小）替代，再删除该前驱 / 后继	两步走

删除度为 2 的结点 50(用中序后继 55 替代):
        50                     55
      /    \                 /    \
    30      70      →      30      70
           /  \                    /  \
          55   80                 60    80
            \
             60

把 55 的值复制到 50 的位置,再删除原 55 结点 ——
此时 55 最多只有右孩子 60,退化为情况 2(度为 1)

【记忆锚点】 “叶子直接摘，独苗顶上来，双枝找替身”——三种情况的口诀。

【易混对比】 “中序前驱”与“中序后继”的定位

名称	位置	特点
中序前驱	左子树中最右的结点	左子树的最大值
中序后继	右子树中最左的结点	右子树的最小值

两者选哪一个替代都可以，结果不同但都保持 BST 性质。国企笔试“树”模块高频考点，常与第 44 题的中序有序性质连考。

【自测】 删除 BST 中度为 2 的结点时，为什么可以用中序前驱 / 后继替代？

答：因为中序前驱是“比它小的元素中最大的”，中序后继是“比它大的元素中最小的”；用它们替代后，左子树全部小于新值、右子树全部大于新值，BST 性质保持不变。与第 44 题连考。

【知识关联】

同库连考：与第 42、44 题（BST 性质）、第 43 题（查找）完整 BST 专题；与第 18 题（链表删除指针）类比「先找到替身再摘」。
工程实现:Java TreeMap.remove 红黑树删除远复杂于 BST 基础删除；数据库索引删除+合并/再平衡。
408 / 国企真题:408 与国网 BST 删除操作。
面试追问:①「为何用中序前驱/后继？」（它们无左孩子或结构更简单）；②「删根？」（同样三种情况）。

【拓展延伸】

完整验算:

叶子:直接删
独苗:孩子顶上
双枝:找中序前驱(左子树最右)或后继(右子树最左)替换关键字,再删那个前驱/后继(必为叶子或独苗)

变式：删除后仍保持 BST 中序有序。

工程应用：符号表删除、内存管理空闲树。

47. 在 n 个元素中求最大的 K 个数(TopK)，当 K 远小于 n 时，最常用的方案及其时间复杂度是( )

标签：【互联网面试高频】

A. 先整体排序再取前 K,O(n log n) B. 维护一个大小为 K 的小顶堆，O(n log K) C. 用哈希表去重后再取前 K D. 用队列依次遍历，O(n)

答案：B【结论】 维护大小为 K 的小顶堆，时间复杂度 O(n log K)，选 B。

【逐项辨析】

A 先整体排序再取前 K:O(n log n)，当 K ≪ n 时明显不如 B。
B 维护大小为 K 的小顶堆：正确。 时间复杂度 O(n log K)，空间 O(K)，且无需把全部数据载入内存。
C 用哈希表去重后再取前 K：哈希表只能去重，不能排序或找最值。
D 用队列依次遍历：队列不具备“维护前 K 大”的能力。

【知识点】 求最大的 K 个数为什么用小顶堆（而不是大顶堆）？

维护一个大小为 K 的小顶堆(堆顶是当前 K 个元素中的最小值)
遍历每个元素 x:
  若堆未满    → 直接入堆
  若 x > 堆顶 → 弹出堆顶,把 x 入堆
  若 x ≤ 堆顶 → 跳过(x 不可能是前 K 大)
遍历结束,堆中即为最大的 K 个数

方案	时间复杂度	空间	是否需全量数据
整体排序	O(n log n)	O(n)	需要
大小为 K 的小顶堆	O(n log K)	O(K)	不需要
快速选择(QuickSelect)	平均 O(n)	O(n)	需要

为什么用小顶堆?—— 堆顶是"门槛"
只要新元素比门槛大,就淘汰门槛、把它请进来。
用小顶堆才能 O(1) 拿到门槛(当前第 K 大);
大顶堆拿到的是最大值,无法做淘汰判断。

【记忆锚点】 “求最大 K 个，用小顶堆当门槛”——堆顶是最小的那个，比它大才有资格进。

【易混对比】 与第 93 题（数据流 TopK）同型：静态数据可先整体建堆或用快速选择，数据流则必须增量维护堆。“大数据 TopK”是互联网笔试最高频考点之一，常与堆排序、快排对比考查。

【自测】 若要求“最小的 K 个数”，应该用大顶堆还是小顶堆？

答：大顶堆。堆顶是当前 K 个中的最大值，新元素比堆顶小才有资格进入。与本题对照记忆。

【知识关联】

同库连考：与第 84/85 题（堆）、第 93 题（数据流 TopK）同型；与第 14 题（单调队列）对比「最值结构选择」。
工程实现:Java PriorityQueue 默认小顶堆；海量数据 TopK「分治+堆」；搜索引擎热词。
408 / 国企真题：国企/互联网笔试常见；408 堆应用。
面试追问:①「求最大 K 个为何小顶堆？」（堆顶是门槛，更大的才能替换）；②「静态数据？」（快速选择 O(n) 平均更优）。

【拓展延伸】

完整验算:

维护大小 K 的小顶堆
遍历 n 个数:若 x > 堆顶,替换并调整 O(log K)
总 O(n log K),空间 O(K)

变式：求最小 K 个 → 大顶堆；两个堆对顶求中位数。

工程应用：实时排行榜、监控报警 Top 错误、广告竞价。

48. 由权值分别为 1、2、3、4、5 的叶子结点构造一棵哈夫曼树，其带权路径长度 WPL 为( )

标签：【国企笔试超高频】

A. 33 B. 30 C. 35 D. 15

答案：A

【结论】 WPL = 33，选 A。

【推导过程】 按哈夫曼算法每次取两个最小权值合并，合并结果作为新结点参与后续比较

第 1 步:1 + 2 = 3      集合变为 {3, 3, 4, 5}
第 2 步:3 + 3 = 6      集合变为 {4, 5, 6}
第 3 步:4 + 5 = 9      集合变为 {6, 9}
第 4 步:6 + 9 = 15     合并完成

构造出的哈夫曼树

              15
            /    \
           6      9
          / \    / \
         3   3   4   5
        / \
       1   2

WPL = 所有新生成结点的权值之和 = 3 + 6 + 9 + 15 = 33。

【验算】 权值 1、2、3、4、5 对应叶子的深度分别为 3、3、2、2、2:

WPL = 1×3 + 2×3 + 3×2 + 4×2 + 5×2 = 3 + 6 + 6 + 8 + 10 = 33   ✓ 结果一致

【逐项辨析】

A 33：正确。 两种算法结果一致。
B 30：合并顺序错（未始终取最小的两个）。
C 35：某步合并顺序错乱。
D 15：这是权值之和(1+2+3+4+5 = 15)，不是 WPL —— 最常见的错误选项。

【知识点】 计算 WPL 的两种方法（互相验算）：

方法	做法	本题
方法 1 · 新结点求和	WPL = 所有新生成结点权值之和	3 + 6 + 9 + 15 = 33
方法 2 · 深度加权	WPL = Σ（叶子权值 × 叶子深度）	1×3+2×3+3×2+4×2+5×2 = 33

两种方法结果必然相同，考试中可用一种算、另一种验算。

【记忆锚点】 “每次挑两个最小的合并，新结点权值累加起来就是 WPL”——方法 1 最快。

【易错提醒】 ①合并时必须始终取当前最小的两个，不能凭感觉搭树；②选项 D(15)是权值之和，不是 WPL，这是最常见的陷阱；③n 个叶子的哈夫曼树共有 2n−1 个结点、没有度为 1 的结点，可用于快速验算（本题 n = 5，共 9 个结点 ✓）。国网、银行科技岗笔试反复考“给权值算 WPL”。

【自测】 权值为 1、2、3、4 的叶子构造哈夫曼树，WPL 是多少？

答：19。合并：1+2=3 → {3,3,4};3+3=6 → {4,6};4+6=10。WPL = 3+6+10 = 19。验算：深度分别为 3、3、2、1，WPL = 1×3+2×3+3×2+4×1 = 19（写成 3、3、2、2 会得 23，与 19 对不上） ✓。与本题同型。

【知识关联】

同库连考：与第 40、41 题（哈夫曼）直接计算题；与第 32 题（完全二叉树叶子）不同树种。
工程实现:Huffman 编码总比特数 = WPL；构造算法用堆。
408 / 国企真题：国网、银行科技岗反复考「给权值算 WPL」。
面试追问:①「权值之和是 WPL 吗？」（不是，那是选项陷阱）；②「两种算法？」（深度×权求和 / 每次合并权累加）。

【拓展延伸】

完整验算:

权 1,2,3,4,5
合并 1+2=3 → 列表 3,3,4,5
合并 3+3=6 → 4,5,6
合并 4+5=9 → 6,9
合并 6+9=15
WPL = 合并中间结果之和 = 3+6+9+15 = 33 ✓

用深度法验算叶子深度 3,3,2,2,2:
1*3+2*3+3*2+4*2+5*2 = 3+6+6+8+10 = 33 ✓

变式：权 1,2,3,4 的 WPL = 19。逐步：合并 1+2=3 → 合并 3+3=6 → 合并 4+6=10；WPL = 各次合并代价之和 = 3+6+10 = 19。

工程应用：压缩率估算、最优合并代价（哈夫曼=石子合并最优）。

49. 判断单链表是否有环，最优算法是( )

标签：【互联网面试高频】

A. 双重循环遍历，时间复杂度 O(n²) B. 用栈记录访问过的节点 C. 将链表反转后再与原链表比较 D. 快慢指针（Floyd 判圈）：快指针每次走 2 步、慢指针每次走 1 步，若相遇则有环

答案：D【结论】 快慢指针（Floyd 判圈）最优，时间复杂度 O(n)、空间 O(1)，选 D。

【逐项辨析】

A 双重循环遍历 O(n²)：用两层循环比较结点地址是否重复，时间代价大。
D 快慢指针（Floyd 判圈）：正确。 时间 O(n)、空间 O(1)，是最优解。
C 将链表反转后再与原链表比较：会破坏原链表结构，且实现复杂。
B 用栈记录访问过的节点：需要 O(n) 额外空间，不如快慢指针。

【知识点】 快慢指针（Floyd 判圈算法）：

快指针 fast 每次走 2 步,慢指针 slow 每次走 1 步
若链表无环 → fast 先到达 NULL,循环结束,判定无环
若链表有环 → fast 最终会追上 slow(相遇),判定有环

为什么一定会相遇？ 进入环后，快指针相对慢指针每轮靠近 1 步，环是有限的，所以必然追上。

找环入口的方法（两步走）：

第 1 步:快慢指针相遇
第 2 步:让 slow 回到头结点,fast 留在相遇点,
       两者改为同速(都走 1 步)前进,
       再次相遇的位置就是环的入口结点

原理：设头到入口距离为 a、入口到相遇点为 b、环长为 c，则相遇时 2(a+b) = a+b+nc，化简得 a = (n−1)c + (c−b)，即“从头走 a 步”与“从相遇点走 c−b 步”同时到达入口。

【记忆锚点】 “快的追慢的，追上了就有环；回起点再同速走，再相遇就是入口”。

【易混对比】 与“求链表中点”对照：同样是快慢指针，但求中点时快指针走 2 步、慢指针走 1 步，快指针到尾时慢指针恰在中点。同一个技巧的两种应用 —— 判环（看是否相遇）与找中点（看快到头时慢的位置）。

【自测】 快慢指针判环的时间复杂度是多少？为什么？

答：O(n)。慢指针最多走 n 步（有环时进入环后也最多再走一个环长），快指针步数是慢指针的 2 倍。LeetCode 141/142，华为 OD、字节、腾讯笔试 / 面试超高频。

【知识关联】

同库连考：与第 18 题（指针操作）、第 12 题（链表遍历）同属链表；LeetCode 141/142。
工程实现:Java 集合遍历时 ConcurrentModificationException 的 fail-fast 用 modCount 不是快慢指针；但判环/找中点广泛用于链表算法与部分垃圾回收「快慢指针找环」。
408 / 国企真题：互联网面试超高频；408 少见。
面试追问:①「为何一定会相遇？」（相对速度 1，有环必套圈）；②「找入口第二阶段为何同速？」（数学可证 2(v+x)=v+x+kc → x = kc−v 等）。

【拓展延伸】

完整验算:

快 2 慢 1,有环则必在环内相遇
找入口:一指 head,一指相遇点,同速走,再遇即入口
时间 O(n),空间 O(1)

变式：求环长（相遇后再走回相遇点计数）；求中点（快到尾时慢在中）。

工程应用：检测循环引用、部分调度算法、Rust 链表面试题。

50. 一棵深度为7的完全二叉树，若第7层有10个节点，则该二叉树的节点总数为( )

标签：【互联网/国企笔试常考】

A. 73 B. 83 C. 117 D. 127

答案：A

【结论】 结点总数为 63 + 10 = 73，选 A。

【推导过程】 深度为 7 的完全二叉树，前 6 层是满的

前 6 层结点数 = 2⁶ − 1 = 64 − 1 = 63
第 7 层结点数 = 10(题目给出)
结点总数 = 63 + 10 = 73

【逐项辨析】

A 73：正确。 63 + 10。
B 83：计算错误（可能把第 7 层当成 20 个）。
C 117：计算错误。
D 127：这是第 7 层满（64 个）时的结点总数 = 2⁷ − 1 = 127，本题第 7 层只有 10 个结点，不能选 D。

【知识点】 完全二叉树的层结点数规律

层号	该层最多结点数	累计结点数
1	1	1
2	2	3
3	4	7
4	8	15
5	16	31
6	32	63
7	64	127

完全二叉树的两条特征（必背）：

除最后一层外，其余各层结点数均达到最大（即前 h−1 层是满的）；
最后一层的结点从左到右连续排列，中间不能有空缺。

【记忆锚点】 “前 h−1 层照满算(2^(h−1) − 1)，最后一层数个数”——求完全二叉树结点数的通用套路。

【易错提醒】 若第 7 层满（64 个），总结点数为 127（选项 D），本题第 7 层未满，不能选 D。另注意：由“第 7 层有 10 个结点”还可推出叶子总数 —— 第 7 层全是叶子；第 6 层中有孩子的结点数为 ⌈10/2⌉ = 5，故第 6 层叶子数为 32 − 5 = 27，总叶子数 = 10 + 27 = 37。

【易混对比】 与第 32 题（完全二叉树叶子数）对照：第 32 题给的是结点总数求叶子数；本题给的是最后一层结点数求结点总数。两者互为逆向，都要用到“前 h−1 层满”这一性质。

【自测】 一棵深度为 8 的完全二叉树，第 8 层有 20 个结点，则结点总数是多少？

答：2⁷ − 1 + 20 = 127 + 20 = 147。与第 32 题连考。

【知识关联】

同库连考：与第 32 题（100 结点叶子 50）公式同源；与第 35 题（深度）、第 33 题（层结点）性质网。
工程实现：堆的最后一层叶子计数、PriorityQueue 建堆从非叶开始。
408 / 国企真题:408 与国网计算。
面试追问:①「n 奇时叶子？」((n+1)/2);②「完全二叉树 101 叶子？」(51)。

【拓展延伸】

完整验算:

n=100 偶 → n₀=n/2=50
n=101 奇 → n₀=(n+1)/2=51
推导:n₁∈{0,1},联立 n=n₀+n₁+n₂, n₀=n₂+1

变式：给高度和最后一层结点数求总结点（前 h−1 层满 + 最后一层）。

工程应用：堆化循环上界 ⌊n/2⌋ 个非叶结点。