图解算法通识讲义树与图
二叉树深度优先与层序遍历
核心心智模型：分而治之，层层递进；前中后序递归是栈，层序遍历是队列，万变不离树根与子树。
核心交互式算法图解演练沙盒
树形递归模型
二叉树中序遍历与递归调用栈演练
步骤 1 / 5
1
2
4
5
3
6
当前递归调用栈 (Call Stack)
▶ dfs(1)
中序遍历输出序列
[]
根节点入栈：访问根节点 1，按照中序遍历 (左-根-右) 规则，递归深入探测左子树。
关键操作与时空复杂度速查对照表
| 操作 / 算法阶段 | 平均时间 | 最坏时间 | 空间复杂度 | 核心底层机制 |
|---|---|---|---|---|
| DFS 递归全量遍历 | O(N) | O(N) | O(H) | H 为树高度，平衡树为 O(log N)，链状退化为 O(N)。 |
| BFS 队列层序遍历 | O(N) | O(N) | O(W) | W 为树的最大宽度，满二叉树最底层包含 N/2 个节点。 |
template.java
Queue<TreeNode> queue = new LinkedList<>();
if (root != null) queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}解题核心心法提炼
- 二叉搜索树（BST）的中序遍历序列必然是严格升序的，验证合法性时只需判断中序是否单调递增。
- 最近公共祖先（LCA）是递归自底向上汇总信息的经典范例。
- 序列化与反序列化通过前序或层序带空指针标记实现树结构与字符串的可逆转换。
常见踩坑警示与避坑指南
- 递归没有写对基底条件（Base Case），未判断 root == null 导致栈溢出。
- 层序遍历中误在循环内直接使用 queue.size() 判断，因为后续入队操作会导致 size 动态变化，破坏层级边界。
对应 Hot 100 实战题目突围
原理已掌握！立即进入沉浸式工作台开始实战演练，强化代码肌肉记忆