1. 项目概述
今天要分享的是LeetCode上两道经典题目：108题"将有序数组转化为二叉树"和203题"移除链表元素"。这两道题分别代表了树和链表这两个数据结构中的基础操作，也是面试中的高频考点。
我刷了300+道LeetCode题目后发现，很多复杂的树和链表问题其实都是基于这些基础操作的变种。掌握好这两道题，不仅能帮你快速解决类似问题，更能深入理解递归思想和指针操作的精髓。
2. 核心需求解析
2.1 有序数组转二叉树（LeetCode 108）
题目要求将一个按照升序排列的有序数组，转换为一棵高度平衡的二叉搜索树。这里有几个关键点需要注意：
- 高度平衡：左右子树的高度差不超过1
- 二叉搜索树：左子树所有节点值 < 根节点值 < 右子树所有节点值
- 有序数组：已经排序好的数组，可以直接利用这个特性
2.2 移除链表元素（LeetCode 203）
题目要求从链表中删除所有等于给定值的节点。看似简单，但实际处理时需要考虑多种边界情况：
- 头节点就是要删除的节点
- 连续多个节点都要删除
- 空链表的情况
- 所有节点都要删除的情况
3. 解题思路与实现
3.1 有序数组转二叉树的递归解法
这道题最直观的解法就是递归。因为要构建平衡BST，我们可以每次都选择数组中间的元素作为根节点：
def sortedArrayToBST(nums): if not nums: return None mid = len(nums) // 2 root = TreeNode(nums[mid]) root.left = sortedArrayToBST(nums[:mid]) root.right = sortedArrayToBST(nums[mid+1:]) return root时间复杂度分析：每次递归都将问题规模减半，所以是O(n)，空间复杂度由于递归栈也是O(logn)。
注意：Python的切片操作nums[:mid]会创建新数组，这在处理大数组时会有额外空间开销。更优的做法是传递索引而不是切片。
3.2 移除链表元素的迭代解法
链表删除操作的关键是处理好指针的指向。我们可以使用哨兵节点(dummy node)来简化头节点的处理：
def removeElements(head, val): dummy = ListNode(0) dummy.next = head prev, curr = dummy, head while curr: if curr.val == val: prev.next = curr.next else: prev = curr curr = curr.next return dummy.next这个解法的时间复杂度是O(n)，空间复杂度是O(1)。
4. 常见问题与优化
4.1 有序数组转二叉树的常见错误
- 忘记处理空数组的情况
- 中间位置计算错误（应该用//而不是/）
- 递归终止条件不完整
- 切片操作导致的空间浪费
优化建议：改用索引传递避免切片
def sortedArrayToBST(nums): def helper(left, right): if left > right: return None mid = (left + right) // 2 root = TreeNode(nums[mid]) root.left = helper(left, mid-1) root.right = helper(mid+1, right) return root return helper(0, len(nums)-1)4.2 移除链表元素的易错点
- 忘记处理头节点就是要删除的情况
- 删除节点后忘记移动prev指针
- 处理连续要删除的节点时逻辑错误
- 空链表未做特殊处理
优化建议：递归解法虽然空间复杂度高，但代码更简洁
def removeElements(head, val): if not head: return None head.next = removeElements(head.next, val) return head.next if head.val == val else head5. 相关题目扩展
掌握了这两道基础题后，可以尝试以下进阶题目：
二叉树相关：
- 有序链表转换二叉搜索树
- 平衡二叉树
- 删除二叉搜索树中的节点
链表相关：
- 删除排序链表中的重复元素 II
- 删除排序链表中的重复元素
- 删除链表的倒数第N个节点
6. 个人刷题心得
在刷了这么多树和链表的题目后，我总结了几个关键点：
- 树的问题90%可以用递归解决，关键是找到递归终止条件和递归关系
- 链表问题多用哨兵节点可以简化边界条件处理
- 画图！画图！画图！重要的事情说三遍，把问题可视化能帮助理解
- 先写伪代码理清思路，再实现细节
- 测试用例要覆盖各种边界情况（空、单节点、全要删除等）
最后一个小技巧：对于树的问题，可以先用小规模的例子（3-5个节点）手动构建一遍，这样能更直观地理解题目要求。
