LeetCode面试经典150题：二叉树与滑动窗口解题技巧

1. LeetCode面试经典150题的价值与定位

作为一名经历过多次大厂面试的开发者，我深刻理解LeetCode在技术面试中的分量。面试经典150题这个精选合集，可以说是求职者准备算法面试的黄金题库。它不像题库里动辄上千道的题目那样让人望而生畏，也不像某些随机刷题那样缺乏针对性。

这个合集的特别之处在于：

• 题目覆盖了面试中最常考的算法和数据结构
• 难度分布合理，既有基础题也有中等难度题
• 每道题都经过精心筛选，具有代表性
• 解决这些问题所需的技巧可以迁移到其他类似题目

我建议的刷题策略是：先完整过一遍这150题，确保每道题都能独立写出正确解法。然后再针对薄弱环节进行专项突破。这样的准备方式比盲目刷几百道题要高效得多。

2. 二叉树类题目的解题框架

二叉树是面试中最常考的数据结构之一，在150题中占比很高。掌握二叉树的解题框架可以事半功倍。

2.1 二叉树遍历的四种基本方式

先序、中序、后序遍历和层次遍历是解决二叉树问题的基础。以Python为例，递归实现非常简单：

# 前序遍历 def preorder(root): if not root: return print(root.val) preorder(root.left) preorder(root.right) # 中序遍历 def inorder(root): if not root: return inorder(root.left) print(root.val) inorder(root.right) # 后序遍历 def postorder(root): if not root: return postorder(root.left) postorder(root.right) print(root.val)

对于迭代实现，我推荐使用栈来模拟递归过程。以中序遍历为例：

def inorderTraversal(root): stack = [] res = [] curr = root while curr or stack: while curr: stack.append(curr) curr = curr.left curr = stack.pop() res.append(curr.val) curr = curr.right return res

2.2 路径和问题的通用解法

路径和问题有多种变体，但核心思路都是DFS遍历。以"路径总和II"为例，需要找出所有从根到叶子的路径和等于目标值的路径：

def pathSum(root, targetSum): res = [] def dfs(node, path, remaining): if not node: return path.append(node.val) if not node.left and not node.right and remaining == node.val: res.append(list(path)) dfs(node.left, path, remaining - node.val) dfs(node.right, path, remaining - node.val) path.pop() dfs(root, [], targetSum) return res

关键点：

1. 使用回溯法记录当前路径
2. 只在叶子节点判断是否满足条件
3. 注意Python中列表是可变对象，需要复制

3. 滑动窗口问题的解题模式

滑动窗口是解决子串/子数组问题的利器，在150题中有多道相关题目。

3.1 固定窗口大小问题

以"滑动窗口最大值"为例，这是道经典难题。暴力解法是O(nk)，而使用双端队列可以达到O(n)：

def maxSlidingWindow(nums, k): from collections import deque q = deque() res = [] for i, num in enumerate(nums): while q and nums[q[-1]] <= num: q.pop() q.append(i) if q[0] == i - k: q.popleft() if i >= k - 1: res.append(nums[q[0]]) return res

这个解法的精妙之处在于：

1. 队列中存储的是索引而非值
2. 队列保持单调递减
3. 及时移除超出窗口范围的元素

3.2 可变窗口大小问题

"最小覆盖子串"是这类问题的代表。解题模板如下：

def minWindow(s, t): from collections import defaultdict need = defaultdict(int) for c in t: need[c] += 1 missing = len(t) left = start = end = 0 for right, c in enumerate(s, 1): if need[c] > 0: missing -= 1 need[c] -= 1 if missing == 0: while left < right and need[s[left]] < 0: need[s[left]] += 1 left += 1 if end == 0 or right - left < end - start: start, end = left, right return s[start:end]

关键点：

1. 使用哈希表记录所需字符及其数量
2. 维护missing计数器
3. 当满足条件时尝试收缩左边界

4. 动态规划问题的分类与解题技巧

动态规划是算法面试的重中之重，150题中有大量DP问题。我将其分为几类：

4.1 单序列DP

"最长递增子序列"是典型代表。O(n^2)解法：

def lengthOfLIS(nums): if not nums: return 0 dp = [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1) return max(dp)

更优的O(nlogn)解法使用二分查找：

def lengthOfLIS(nums): tails = [] for num in nums: left, right = 0, len(tails) while left < right: mid = (left + right) // 2 if tails[mid] < num: left = mid + 1 else: right = mid if left == len(tails): tails.append(num) else: tails[left] = num return len(tails)

4.2 双序列DP

"编辑距离"是经典的双序列DP问题：

def minDistance(word1, word2): m, n = len(word1), len(word2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j for i in range(1, m + 1): for j in range(1, n + 1): if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) return dp[m][n]

4.3 背包问题

"零钱兑换"是典型的完全背包问题：

def coinChange(coins, amount): dp = [float('inf')] * (amount + 1) dp[0] = 0 for coin in coins: for i in range(coin, amount + 1): dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] != float('inf') else -1

5. 面试中的实战技巧

刷题只是准备的一部分，面试中的表现同样重要。根据我的面试经验，分享几个实用技巧：

5.1 解题步骤的规范化

1. 明确问题：复述题目要求，确认理解正确
2. 举例说明：用具体例子演示输入输出
3. 暴力解法：先给出最直观的解法
4. 优化思路：分析时间/空间复杂度，提出优化方向
5. 代码实现：写出清晰可读的代码
6. 测试用例：用边缘案例测试代码

5.2 代码风格建议

• 变量命名要有意义，避免单字母命名
• 适当添加注释，特别是复杂逻辑
• 保持一致的缩进和格式
• 优先使用语言内置函数和数据结构
• 处理边界条件要谨慎

5.3 常见问题应对

当遇到不会的问题时：

1. 保持冷静，不要慌张
2. 尝试分解问题，从简单情况开始
3. 与面试官交流思路，寻求提示
4. 即使无法完全解决，也要展示思考过程

6. 高频面试题精讲

6.1 对称二叉树

判断二叉树是否对称的递归解法：

def isSymmetric(root): def helper(left, right): if not left and not right: return True if not left or not right: return False return left.val == right.val and helper(left.left, right.right) and helper(left.right, right.left) return helper(root, root)

迭代解法使用队列：

def isSymmetric(root): queue = [root, root] while queue: t1 = queue.pop(0) t2 = queue.pop(0) if not t1 and not t2: continue if not t1 or not t2: return False if t1.val != t2.val: return False queue.append(t1.left) queue.append(t2.right) queue.append(t1.right) queue.append(t2.left) return True

6.2 LRU缓存机制

使用有序字典的简单实现：

from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.cache = OrderedDict() self.capacity = capacity def get(self, key): if key not in self.cache: return -1 self.cache.move_to_end(key) return self.cache[key] def put(self, key, value): if key in self.cache: self.cache.move_to_end(key) self.cache[key] = value if len(self.cache) > self.capacity: self.cache.popitem(last=False)

手动实现哈希表+双向链表的完整版本：

class DLinkedNode: def __init__(self, key=0, value=0): self.key = key self.value = value self.prev = None self.next = None class LRUCache: def __init__(self, capacity): self.cache = dict() self.head = DLinkedNode() self.tail = DLinkedNode() self.head.next = self.tail self.tail.prev = self.head self.capacity = capacity self.size = 0 def get(self, key): if key not in self.cache: return -1 node = self.cache[key] self.moveToHead(node) return node.value def put(self, key, value): if key in self.cache: node = self.cache[key] node.value = value self.moveToHead(node) else: node = DLinkedNode(key, value) self.cache[key] = node self.addToHead(node) self.size += 1 if self.size > self.capacity: removed = self.removeTail() self.cache.pop(removed.key) self.size -= 1 def addToHead(self, node): node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node def removeNode(self, node): node.prev.next = node.next node.next.prev = node.prev def moveToHead(self, node): self.removeNode(node) self.addToHead(node) def removeTail(self): node = self.tail.prev self.removeNode(node) return node

7. 刷题计划与资源推荐

7.1 150题刷题路线图

我建议按照以下顺序刷题：

1. 数组和字符串（20天）
2. 链表（10天）
3. 二叉树（15天）
4. 图论（10天）
5. 动态规划（20天）
6. 其他杂项（5天）

每天保持3-5题的节奏，重点题目要反复练习。

7.2 辅助工具推荐

1. LeetCode官方解题讨论区 - 查看高质量题解
2. VisuAlgo - 可视化算法执行过程
3. 算法导论 - 系统学习算法理论
4. 代码随想录 - 分类整理的LeetCode题解

7.3 面试前的最后准备

1. 复习常见的数据结构实现
2. 重做高频面试题
3. 模拟面试练习
4. 准备项目经历中的算法相关问题
5. 调整作息，保持良好状态