第3章 链表、二叉树、排序、查找、动态规划
本章聚焦 Python 面试中高频的数据结构与算法题，覆盖链表、二叉树、排序、查找及动态规划五大模块。掌握每类问题的核心框架和回答逻辑，能够帮助你快速构建解题思路，避开常见陷阱。
📌 知识结构：常见算法复杂度对比
| 算法/操作 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 链表查找 | O(n) | O(n) | O(1) | — |
| 二叉树搜索 | O(log n) | O(n) | O(1) | — |
📌 面试问题 1：合并两个有序链表
问题：将两个升序链表合并为一个新的升序链表并返回。
🎯 面试官考察点
- 链表基础操作（指针移动、dummy 节点）
- 递归与迭代两种思路的掌握
- 边界处理（空链表、单节点）
🧠 回答框架
- 明确问题：输入两个有序链表头节点，输出合并后的头节点。
- 选择方法：迭代法（dummy 头 + 双指针）或递归法。
- 实现：遍历两链表比较当前值，较小者接入结果链表，指针后移。
- 复杂度：时间 O(n+m)，空间 O(1)（迭代）或 O(n+m)（递归栈）。
- 测试：一个空链表、两链表等长、重复值等。
✍️ 简短示例回答
“我用迭代法，创建 dummy 节点简化头处理。双指针遍历两个链表，比较当前 node.val，较小者接入结果链表，指针后移。最后将剩余部分直接接上。时间复杂度 O(n+m)，空间 O(1)。注意处理空链表边界。”
（约 95 字）
🔍 可能追问
- 递归版本如何写？空间复杂度差别？
- 如果链表有环如何处理？
- 如何合并 k 个有序链表？（优先队列）
⚠️ 避坑提醒：别忘记最后把剩余链表直接拼接，避免逐节点遍历；递归法注意 Python 默认递归深度限制。
📌 面试问题 2：二叉树的最大深度
问题：给定一个二叉树，找出其最大深度（根节点到最远叶子节点的路径上节点数）。
🎯 面试官考察点
- 递归思维（分治）与树遍历基础
- DFS 与 BFS 的区别
- 递归返回值的正确计算
🧠 回答框架
- 理解：深度 = 1 + max(左子树深度, 右子树深度)，空节点深度为 0。
- 方法：递归后序遍历（自底向上）最简洁。
- 实现：if not root: return 0; 递归计算左右深度，返回较大者+1。
- 复杂度：时间 O(n)，空间 O(height)（递归栈）。
- 测试：单节点、斜树（退化为链表）。
✍️ 简短示例回答
“采用递归法：若节点为空返回 0，否则分别计算左右子树深度，取较大值加 1 返回。时间复杂度 O(n)，空间 O(h)。也可用 BFS 层次遍历，但代码更复杂。”
（约 75 字）
🔍 可能追问
- 非递归如何实现？（栈模拟后序 / 层次遍历）
- 二叉树的最小深度如何处理？（注意叶子节点定义）
- 如何判断平衡二叉树？
⚠️ 避坑提醒：最小深度不能简单用 max 改为 min，必须计算到叶子节点；递归层数可能超过 Python 默认栈深度（1000），可考虑迭代显式栈。
📌 面试问题 3：爬楼梯（LeetCode 70）
问题：每次可以爬 1 或 2 个台阶，爬到第 n 阶有多少种不同方法？
🎯 面试官考察点
- 动态规划状态定义与转移方程
- 空间优化（滚动变量代替数组）
- 是否理解 DP 本质（斐波那契数列）
🧠 回答框架
- 定义状态：dp[i] 表示到达第 i 阶的方法数。
- 转移方程：dp[i] = dp[i-1] + dp[i-2]。
- 初始化：dp[1]=1, dp[2]=2。
- 优化：只用两个变量滚动迭代，空间 O(1)。
- 测试：n=0（边界）、n=3（3 种方法）。
✍️ 简短示例回答
“定义 dp[i] 为爬上第 i 阶的方法数。由于最后一步只能从 i-1 或 i-2 过来，所以 dp[i]=dp[i-1]+dp[i-2]。初始化 dp[1]=1, dp[2]=2，用两个变量迭代，时间 O(n)，空间 O(1)。”
（约 90 字）
🔍 可能追问
- 如果每次可以爬 1/2/3 阶，转移方程变化？
- 如何输出所有爬法？（回溯/路径记录）
- 大数情况下如何处理取模？
⚠️ 避坑提醒：n=0 时方法数应为 1（不爬也是一种），但题目通常从 n≥1 开始，要确认边界；空间优化时注意更新顺序，避免覆盖。
💡 面试建议：链表、二叉树和动态规划是大厂面试最高频的三类题目。熟练掌握递归与迭代的切换、DP 状态定义技巧，并提前练习手写代码，能够显著提高通过率。