二叉树
二叉树中每个节点最多有两个有次序的孩子，通常称为左孩子和右孩子。二叉树描述结构，并不自动保证节点值有序或树高接近对数。
1. 面试核心
先记住这几条，再读正文- 前序、中序、后序的区别是根节点相对左右子树的访问位置。
- 遍历 n 个节点需要 O(n)，递归辅助空间为 O(h)，h 为树高。
- 完全二叉树限制形状，二叉搜索树限制值的顺序，两种条件互不替代。
2. 递归结构与遍历
一棵非空二叉树由根、左子树和右子树组成，子树仍是二叉树。空节点提供递归终止条件。
4
/ \
2 7
\
3
这棵树的前序是 4,2,3,7，中序是 2,3,4,7，后序是 3,2,7,4。中序结果在本例有序，是因为该树同时满足搜索树约束；普通二叉树不保证这个结果。
3. 高度与空间
约定空树高度为 0，叶节点高度为 1，则 height(node) = 1 + max(height(left), height(right))。每个节点仅计算一次，时间 O(n)。函数返回后无需保留已完成子树的调用帧，所以递归额外空间由最长路径 h 决定。
当树退化成链，h=n；当形状平衡时，h 为 O(log n)。按层遍历使用队列，空间则由最大层宽决定，不能把所有树遍历都写成 O(log n) 空间。
4. 使用边界
完全二叉树除最后一层外均填满，最后一层从左向右连续。它适合紧凑地存入数组，是二叉堆常用的形状。极不规则的树若直接使用完全树的数组下标规则，会浪费大量空位。
树形输入可能为空、只有根、只有单侧孩子。读取真实对象关系时还应确认没有环和共享子节点，否则它已经需要按图处理。遍历实现见树与图搜索。
5 · 面试题卡片
先想答案，再翻面题目来自公开面经。点任意一张进入翻卡，可左右切换，看完回到这里。
逐张翻看 1 张 →5.1 二叉树遍历的时间和空间复杂度分别由什么决定？
出现公司：暂无已核验的公开来源（本站自测）
考察重点：节点数、树高与层宽分别对遍历成本的影响。
参考回答
完整遍历每个节点一次，时间 O(n)。递归 DFS 的同时活动调用帧由树高 h 决定，空间 O(h)，退化树可达 O(n)。BFS 的队列保存当前和下一层的节点，峰值与层宽相关，最坏 O(n)。平衡树也可能很宽，不能把 BFS 的空间写成 O(log n)。