二叉树
二叉树中每个节点最多有两个有次序的孩子。本文负责遍历、树高、形状和遍历序列重建。
1. 面试核心
先记住这几条，再读正文- 遍历顺序。 前序、中序、后序分别在两子树之前、中间、之后访问根。
- 遍历成本。 遍历 n 个节点需 O(n) 时间。递归 DFS 的额外空间为 O(h)，取决于树高；BFS 的额外空间取决于最大层宽。卡 · 高度与空间
- 完全二叉树。 完全二叉树除最后一层外均填满，最后一层从左到右连续填充，因此可以紧凑地用数组表示。
- 序列重建。 节点值互异时，合法的前序与中序可唯一重建二叉树。卡 · 遍历序列重建
2. 递归结构与遍历
非空二叉树由根、左子树和右子树组成。空节点是递归的终点。
4
/ \
2 7
\
3
前序为 4,2,3,7，中序为 2,3,4,7。后序为 3,2,7,4。本例的中序有序，因为它同时满足 BST 条件。键的顺序约束见二叉搜索树。
3. 高度与空间
约定空树高度为 0，叶节点高度为 1。高度公式为 height(x)=1+max(height(x.left),height(x.right))。每个节点计算一次，时间为 O(n)。
递归只保留当前路径的活动调用帧，空间为 O(h)。链状树的 h=n，平衡树的 h 为 O(log n)。BFS 队列同时容纳相邻两层的部分节点。其空间为 O(w)，w 是最大层宽。
4. 遍历序列重建
节点值互异时，前序首项确定根。根在中序中的位置将左右子树分开。按左子树大小切分前序，再递归处理两个区间。
前序 1,2、中序 2,1 表示根 1 的左孩子为 2。若中序改为 1,2，2 就成为右孩子。两棵树的后序都是 2,1。因此，仅前序与后序会丢失单孩子的方向。
重建时用哈希表记录中序下标，并传递区间。哈希访问期望 O(1) 时，总时间为 O(n)。反复线性寻找根最坏为 O(n²)。重复值需要额外身份信息，或接受重建结果有歧义。
5. 使用边界
完全二叉树除最后一层外均填满。最后一层从左到右连续，适合紧凑数组布局。完美二叉树的所有层都填满，高度 h 时有 2^h-1 个节点。满分支二叉树则要求每个节点有 0 或 2 个孩子。面试中的“满二叉树”应先确认采用哪种定义。
真实对象关系需确认没有环和共享子节点。存在这些关系时，应按图处理。
6 · 面试题卡片
本页题目与参考回答
6.1 二叉树遍历的时间与空间由什么决定？
考察重点：节点数、树高和层宽。
相关内容：高度与空间。
参考回答
完整遍历的时间为 O(n)，DFS 的额外空间取决于树高 h，BFS 的额外空间取决于最大层宽 w。
每个节点只处理一次，因此时间线性。递归 DFS 同时保存一条调用路径，空间为 O(h)，链状树可达 O(n)；BFS 保存待访问的一层节点，空间为 O(w)，完美二叉树可达 O(n)。
6.2 哪些遍历序列能唯一重建二叉树？
考察重点：根定位、子树切分和单孩子歧义。
相关内容：遍历序列重建。
参考回答
值互异时，合法的前序加中序可以唯一重建。
后序加中序也可以，根取后序末项。前序加后序缺少单孩子方向信息。含重复值时需额外区分节点身份。