信息技术大学
树进阶
数据结构与算法·面试高频 · 第 2 章 树与图
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
信息技术大学
树进阶
数据结构与算法·面试高频 · 第 2 章 树与图
最近公共祖先 LCA
LCA 是两条上溯路径的第一个岔口：普通二叉树递归分治，BST 走大小可偷懒。
一般树
左右各自找 p、q，两侧都命中即当前节点
BST 捷径
p、q 分居根两侧即答案，同侧就往下走
带父指针
化成两条链求交点，或集合记祖先比对
字典树 Trie
前缀共享一棵树：插入、查词、查前缀都是走字符的路，公共前缀白送。
节点结构
children 映射加 isEnd 标记，边即字符
三大操作
插入、查整词、查前缀，均 O(词长)
场景
搜索联想、词频统计、拼单词游戏
序列化与反序列化
树变字符串再变回来：前序加空位标记可唯一重建，层序同理。
前序串化
空节点记占位符，分隔符隔开各值
反序列化
按序消费 token，占位即空，递归重建
层序版
队列逐层、空位占位，与层序遍历同构
本节要点
- ✓LCA：两侧都中即祖先，BST 走大小
- ✓Trie：前缀共享，操作 O(词长)
- ✓序列化：空位标记才能唯一重建
延伸主题：手写 BST 版 LCA实现一个 Trie
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1一般二叉树的 LCA 递归为什么成立？
参考答案后序自底向上：左子树找到 p 或 q 就返回它，右侧同样；某节点两侧都非空，说明 p、q 分居两侧，它正是最近公共祖先；一侧为空则答案随另一侧上浮。
2为什么序列化必须记录空节点才能唯一重建？
参考答案只含值的前序序列对应多棵不同的树；空节点占位后，每个节点左右子树的边界完全确定，递归消费 token 才能无歧义地还原原树。
3Trie 相比哈希表存单词，优势场景在哪？
参考答案前缀类查询是哈希表的盲区：Trie 支持前缀搜索、按字典序枚举、自动补全，且公共前缀共享存储；代价是字符级节点多、内存开销大，量大时需压缩。