02.4.1 二叉树与遍历
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.4 树与图
这个知识域解决什么问题
树是层次结构的核心载体。本知识域围绕一条主线展开:二叉树结构与递归遍历 → BST 与平衡树 → 二叉树构造与变换 → 堆与 Trie 树。所有题目先讲清遍历位置与信息依赖,再给可运行代码、复杂度口径与边界用例。
知识地图
二叉树结构与递归遍历(1)
→ BST 与平衡树(2)
→ 二叉树构造与变换(3)
→ 堆与 Trie 树(4)
子主题
| 编号 | 子主题 | 核心内容 | 题数 |
|---|---|---|---|
| 02.4.1.1 | 二叉树结构与递归遍历 | 树术语、前中后序递归/迭代、层序、Morris、深度/平衡/直径/路径和、递归选型与边界 | 20 |
| 02.4.1.2 | BST 与平衡树 | BST 查找/插入/删除、区间验证、中序有序、BST-LCA、有序数组转树、第 K 小、前驱后继、AVL/红黑树概念 | 20 |
| 02.4.1.3 | 二叉树构造与变换 | 前/后序 + 中序构造、翻转、对称、合并、拉平链表、右视图、序列化、子树判断、普通树 LCA | 20 |
| 02.4.1.4 | 堆与 Trie 树 | 堆数组表示、上浮下沉、建堆 O(n)、Top-K、Trie 插入/查询/前缀/删除/计数、通配匹配、最大异或 | 20 |
合计 80 题。 每题按「一句话结论 → 概念解释 → 原理流程 → 代码/图示 → 常见误区 → 追问(带答案)」组织;代码以 Java 为主,标注复杂度口径与边界条件。
学习路径
先 1 掌握三种遍历与递归思维,再 2 利用 BST 有序性处理查找、构造与第 K 小,3 练熟序列构造与指针变换,最后 4 掌握堆与 Trie 两类特殊树结构。
自检
- [ ] 能手写前中后序递归与迭代、层序遍历,并报出空间口径
- [ ] 能用上下界区间验证 BST,写出 BST 查找/插入/删除
- [ ] 能从前序 + 中序递归构造二叉树并切对区间
- [ ] 能写普通二叉树 LCA 后序递归与对称判断
- [ ] 能说清建堆 O(n) 与 Top-K 堆方向选择
- [ ] 能实现 Trie 插入、完整单词查询与前缀匹配
- [ ] 每题能报出时间、空间与口径,并列边界用例