1. 二叉树算法精要从LeetCode Hot 100看核心解题框架刷过LeetCode的朋友都知道二叉树问题是高频考点中的钉子户。最近系统整理了LeetCode Hot 100中的二叉树题目发现其中近20%都与树结构相关。这些题目看似变化多端实则存在通用解法模式。今天我就结合实战经验拆解二叉树问题的五大核心解题框架并附上高频题目的变形解法。提示本文所有代码示例基于Python实现但解题思路适用于任何语言。建议配合LeetCode题目编号同步练习1.1 为什么二叉树总在面试中出现二叉树之所以成为面试常客主要因为其完美覆盖了算法考察的多个维度递归思维的直观体现每个节点都是相同结构的子问题指针操作的经典场景左右子树引用时间复杂度分析的典型样本平衡 vs 非平衡树多种算法思想的结合体DFS/BFS/分治/回溯以Hot 100中的104.二叉树最大深度为例表面考察递归实现实则暗藏对分治思想的理解def maxDepth(root): if not root: return 0 return 1 max(maxDepth(root.left), maxDepth(root.right))2. 二叉树遍历的三种武器2.1 递归遍历最直观的解法模板前序/中序/后序遍历的递归写法是必须掌握的肌肉记忆。以94.二叉树的中序遍历为例def inorderTraversal(root): res [] def dfs(node): if not node: return dfs(node.left) # 左 res.append(node.val) # 中 dfs(node.right) # 右 dfs(root) return res避坑指南递归解法在极端情况下如斜树会导致栈溢出。Python默认递归深度约1000层对应约完全平衡树的10层2.2 迭代遍历显式栈模拟递归面试官常要求用迭代实现递归算法。144.前序遍历的迭代版本def preorderTraversal(root): res [] stack [root] while stack: node stack.pop() if node: res.append(node.val) stack.append(node.right) # 右子先入栈 stack.append(node.left) # 左子后入栈 return res2.3 Morris遍历O(1)空间的魔法算法对于98.验证二叉搜索树这种需要中序遍历的题目Morris算法能在O(1)空间完成def isValidBST(root): prev float(-inf) while root: if root.left: # 找前驱节点 predecessor root.left while predecessor.right and predecessor.right ! root: predecessor predecessor.right if not predecessor.right: predecessor.right root # 建立线索 root root.left else: if root.val prev: return False prev root.val predecessor.right None # 拆除线索 root root.right else: if root.val prev: return False prev root.val root root.right return True3. 高频题型解题框架3.1 路径和问题112/113/437这类问题的通用解法是前缀和哈希表。以437.路径总和III为例def pathSum(root, targetSum): from collections import defaultdict prefix defaultdict(int) prefix[0] 1 count 0 def dfs(node, curr_sum): nonlocal count if not node: return curr_sum node.val count prefix[curr_sum - targetSum] prefix[curr_sum] 1 dfs(node.left, curr_sum) dfs(node.right, curr_sum) prefix[curr_sum] - 1 dfs(root, 0) return count3.2 构造二叉树105/106/889前序中序构造是经典问题。105.从前序与中序遍历序列构造二叉树def buildTree(preorder, inorder): if not preorder: return None root_val preorder[0] root TreeNode(root_val) idx inorder.index(root_val) root.left buildTree(preorder[1:1idx], inorder[:idx]) root.right buildTree(preorder[1idx:], inorder[idx1:]) return root优化技巧先用哈希表存储中序索引避免每次线性查找3.3 最近公共祖先236/235LCA问题有通用解法框架。236.二叉树的最近公共祖先def lowestCommonAncestor(root, p, q): if not root or root p or root q: return root left lowestCommonAncestor(root.left, p, q) right lowestCommonAncestor(root.right, p, q) if left and right: return root return left if left else right对于BST情况235题可以利用有序性优化def lowestCommonAncestor(root, p, q): while root: if root.val max(p.val, q.val): root root.left elif root.val min(p.val, q.val): root root.right else: return root return None4. 二叉树进阶技巧4.1 序列化与反序列化297二叉树的序列化需要处理空指针。297.二叉树的序列化与反序列化def serialize(root): if not root: return None return str(root.val) , serialize(root.left) , serialize(root.right) def deserialize(data): def helper(queue): val queue.popleft() if val None: return None node TreeNode(int(val)) node.left helper(queue) node.right helper(queue) return node return helper(deque(data.split(,)))4.2 二叉树转链表114114.二叉树展开为链表的Morris变种解法def flatten(root): while root: if root.left: predecessor root.left while predecessor.right: predecessor predecessor.right predecessor.right root.right root.right root.left root.left None root root.right4.3 视图类问题199/102199.二叉树的右视图使用层序遍历的变种def rightSideView(root): if not root: return [] res [] from collections import deque q deque([root]) while q: size len(q) for i in range(size): node q.popleft() if i size - 1: res.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) return res5. 二叉树调试技巧5.1 可视化打印工具开发时可以使用以下工具快速验证树结构def printTree(root): from collections import deque q deque([root]) while q: level [] for _ in range(len(q)): node q.popleft() level.append(str(node.val) if node else null) if node: q.append(node.left) q.append(node.right) print( .join(level))5.2 测试用例构造方法二叉树测试用例构造模板def build_test_tree(): # 1 # / \ # 2 3 # / \ \ # 4 5 6 root TreeNode(1) root.left TreeNode(2) root.right TreeNode(3) root.left.left TreeNode(4) root.left.right TreeNode(5) root.right.right TreeNode(6) return root5.3 常见错误排查指针未判空在访问node.left/right前忘记检查node是否为None递归终止条件缺失导致无限递归栈溢出修改结构时断链如在flatten过程中未保存原右子树引用比较错误BST判断时误用严格小于/大于我在实际刷题中发现二叉树问题的解题时间与画图时间成反比。建议先在纸上画出至少3层的示例树标注遍历路径或操作步骤再动手编码。对于Morris遍历这类复杂算法可以用小树3-5个节点逐步模拟指针变化过程 LeetCode二叉树算法精要：核心解题框架与高频题型
1. 二叉树算法精要从LeetCode Hot 100看核心解题框架刷过LeetCode的朋友都知道二叉树问题是高频考点中的钉子户。最近系统整理了LeetCode Hot 100中的二叉树题目发现其中近20%都与树结构相关。这些题目看似变化多端实则存在通用解法模式。今天我就结合实战经验拆解二叉树问题的五大核心解题框架并附上高频题目的变形解法。提示本文所有代码示例基于Python实现但解题思路适用于任何语言。建议配合LeetCode题目编号同步练习1.1 为什么二叉树总在面试中出现二叉树之所以成为面试常客主要因为其完美覆盖了算法考察的多个维度递归思维的直观体现每个节点都是相同结构的子问题指针操作的经典场景左右子树引用时间复杂度分析的典型样本平衡 vs 非平衡树多种算法思想的结合体DFS/BFS/分治/回溯以Hot 100中的104.二叉树最大深度为例表面考察递归实现实则暗藏对分治思想的理解def maxDepth(root): if not root: return 0 return 1 max(maxDepth(root.left), maxDepth(root.right))2. 二叉树遍历的三种武器2.1 递归遍历最直观的解法模板前序/中序/后序遍历的递归写法是必须掌握的肌肉记忆。以94.二叉树的中序遍历为例def inorderTraversal(root): res [] def dfs(node): if not node: return dfs(node.left) # 左 res.append(node.val) # 中 dfs(node.right) # 右 dfs(root) return res避坑指南递归解法在极端情况下如斜树会导致栈溢出。Python默认递归深度约1000层对应约完全平衡树的10层2.2 迭代遍历显式栈模拟递归面试官常要求用迭代实现递归算法。144.前序遍历的迭代版本def preorderTraversal(root): res [] stack [root] while stack: node stack.pop() if node: res.append(node.val) stack.append(node.right) # 右子先入栈 stack.append(node.left) # 左子后入栈 return res2.3 Morris遍历O(1)空间的魔法算法对于98.验证二叉搜索树这种需要中序遍历的题目Morris算法能在O(1)空间完成def isValidBST(root): prev float(-inf) while root: if root.left: # 找前驱节点 predecessor root.left while predecessor.right and predecessor.right ! root: predecessor predecessor.right if not predecessor.right: predecessor.right root # 建立线索 root root.left else: if root.val prev: return False prev root.val predecessor.right None # 拆除线索 root root.right else: if root.val prev: return False prev root.val root root.right return True3. 高频题型解题框架3.1 路径和问题112/113/437这类问题的通用解法是前缀和哈希表。以437.路径总和III为例def pathSum(root, targetSum): from collections import defaultdict prefix defaultdict(int) prefix[0] 1 count 0 def dfs(node, curr_sum): nonlocal count if not node: return curr_sum node.val count prefix[curr_sum - targetSum] prefix[curr_sum] 1 dfs(node.left, curr_sum) dfs(node.right, curr_sum) prefix[curr_sum] - 1 dfs(root, 0) return count3.2 构造二叉树105/106/889前序中序构造是经典问题。105.从前序与中序遍历序列构造二叉树def buildTree(preorder, inorder): if not preorder: return None root_val preorder[0] root TreeNode(root_val) idx inorder.index(root_val) root.left buildTree(preorder[1:1idx], inorder[:idx]) root.right buildTree(preorder[1idx:], inorder[idx1:]) return root优化技巧先用哈希表存储中序索引避免每次线性查找3.3 最近公共祖先236/235LCA问题有通用解法框架。236.二叉树的最近公共祖先def lowestCommonAncestor(root, p, q): if not root or root p or root q: return root left lowestCommonAncestor(root.left, p, q) right lowestCommonAncestor(root.right, p, q) if left and right: return root return left if left else right对于BST情况235题可以利用有序性优化def lowestCommonAncestor(root, p, q): while root: if root.val max(p.val, q.val): root root.left elif root.val min(p.val, q.val): root root.right else: return root return None4. 二叉树进阶技巧4.1 序列化与反序列化297二叉树的序列化需要处理空指针。297.二叉树的序列化与反序列化def serialize(root): if not root: return None return str(root.val) , serialize(root.left) , serialize(root.right) def deserialize(data): def helper(queue): val queue.popleft() if val None: return None node TreeNode(int(val)) node.left helper(queue) node.right helper(queue) return node return helper(deque(data.split(,)))4.2 二叉树转链表114114.二叉树展开为链表的Morris变种解法def flatten(root): while root: if root.left: predecessor root.left while predecessor.right: predecessor predecessor.right predecessor.right root.right root.right root.left root.left None root root.right4.3 视图类问题199/102199.二叉树的右视图使用层序遍历的变种def rightSideView(root): if not root: return [] res [] from collections import deque q deque([root]) while q: size len(q) for i in range(size): node q.popleft() if i size - 1: res.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) return res5. 二叉树调试技巧5.1 可视化打印工具开发时可以使用以下工具快速验证树结构def printTree(root): from collections import deque q deque([root]) while q: level [] for _ in range(len(q)): node q.popleft() level.append(str(node.val) if node else null) if node: q.append(node.left) q.append(node.right) print( .join(level))5.2 测试用例构造方法二叉树测试用例构造模板def build_test_tree(): # 1 # / \ # 2 3 # / \ \ # 4 5 6 root TreeNode(1) root.left TreeNode(2) root.right TreeNode(3) root.left.left TreeNode(4) root.left.right TreeNode(5) root.right.right TreeNode(6) return root5.3 常见错误排查指针未判空在访问node.left/right前忘记检查node是否为None递归终止条件缺失导致无限递归栈溢出修改结构时断链如在flatten过程中未保存原右子树引用比较错误BST判断时误用严格小于/大于我在实际刷题中发现二叉树问题的解题时间与画图时间成反比。建议先在纸上画出至少3层的示例树标注遍历路径或操作步骤再动手编码。对于Morris遍历这类复杂算法可以用小树3-5个节点逐步模拟指针变化过程