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 res2.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关键点使用回溯法记录当前路径只在叶子节点判断是否满足条件注意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这个解法的精妙之处在于队列中存储的是索引而非值队列保持单调递减及时移除超出窗口范围的元素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]关键点使用哈希表记录所需字符及其数量维护missing计数器当满足条件时尝试收缩左边界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 -15. 面试中的实战技巧刷题只是准备的一部分面试中的表现同样重要。根据我的面试经验分享几个实用技巧5.1 解题步骤的规范化明确问题复述题目要求确认理解正确举例说明用具体例子演示输入输出暴力解法先给出最直观的解法优化思路分析时间/空间复杂度提出优化方向代码实现写出清晰可读的代码测试用例用边缘案例测试代码5.2 代码风格建议变量命名要有意义避免单字母命名适当添加注释特别是复杂逻辑保持一致的缩进和格式优先使用语言内置函数和数据结构处理边界条件要谨慎5.3 常见问题应对当遇到不会的问题时保持冷静不要慌张尝试分解问题从简单情况开始与面试官交流思路寻求提示即使无法完全解决也要展示思考过程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 True6.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(lastFalse)手动实现哈希表双向链表的完整版本class DLinkedNode: def __init__(self, key0, value0): 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 node7. 刷题计划与资源推荐7.1 150题刷题路线图我建议按照以下顺序刷题数组和字符串20天链表10天二叉树15天图论10天动态规划20天其他杂项5天每天保持3-5题的节奏重点题目要反复练习。7.2 辅助工具推荐LeetCode官方解题讨论区 - 查看高质量题解VisuAlgo - 可视化算法执行过程算法导论 - 系统学习算法理论代码随想录 - 分类整理的LeetCode题解7.3 面试前的最后准备复习常见的数据结构实现重做高频面试题模拟面试练习准备项目经历中的算法相关问题调整作息保持良好状态