LeetCode二叉树高频题型解析与优化技巧-育师

1. 二叉树基础概念回顾

在正式进入LeetCode Hot 100二叉树专题的第三部分之前，我们需要先夯实几个核心概念。二叉树作为数据结构中的常青树，其重要性不言而喻。一棵标准的二叉树由节点组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树常见的几种特殊形态值得特别注意：

满二叉树：每个节点都有0个或2个子节点
完全二叉树：除最后一层外，其他层节点都达到最大数，且最后一层节点都集中在左侧
二叉搜索树(BST)：左子树所有节点值小于根节点，右子树所有节点值大于根节点
平衡二叉树(AVL)：任意节点的左右子树高度差不超过1

提示：理解这些特殊二叉树的特性，对解决LeetCode题目至关重要。很多题目都会基于这些特性设计考察点。

2. Hot 100二叉树高频题型解析

2.1 二叉树路径问题

路径问题是二叉树题目中的经典题型，通常要求找到满足特定条件的路径。这类题目往往需要结合深度优先搜索(DFS)和回溯思想。

以LeetCode 113题"路径总和II"为例：

题目要求找出所有从根节点到叶子节点路径总和等于给定目标和的路径
核心解法是前序遍历配合路径记录
关键点在于递归返回时要撤销当前节点的选择（回溯）

def pathSum(root, targetSum): res = [] def dfs(node, path, remain): if not node: return path.append(node.val) if not node.left and not node.right and remain == node.val: res.append(list(path)) dfs(node.left, path, remain - node.val) dfs(node.right, path, remain - node.val) path.pop() # 关键回溯步骤 dfs(root, [], targetSum) return res

2.2 二叉树序列化与反序列化

序列化是将二叉树转换为字符串表示的过程，反序列化则是将字符串恢复为原始二叉树结构。LeetCode 297题就是这类问题的典型代表。

序列化方案通常有两种主流选择：

前序遍历序列化：根-左-右的顺序
层序遍历序列化：按层级顺序存储

前序遍历方案的实现要点：

使用特殊符号(如"#")表示空节点
节点值之间用分隔符(如",")隔开
反序列化时同样按照前序顺序重建

def serialize(root): if not root: return '#' return str(root.val) + ',' + serialize(root.left) + ',' + serialize(root.right) def deserialize(data): nodes = data.split(',') def build(): val = nodes.pop(0) if val == '#': return None node = TreeNode(int(val)) node.left = build() node.right = build() return node return build()

2.3 二叉树最近公共祖先(LCA)

寻找二叉树中两个节点的最近公共祖先是一类高频题目，LeetCode 236题就是典型代表。解决这类问题有几种常见思路：

递归法：
- 如果当前节点是p或q，返回当前节点
- 递归查询左右子树
- 如果左右子树都找到，当前节点就是LCA
- 否则返回非空的那一侧结果
父指针法：
- 先遍历记录每个节点的父节点
- 从p节点向上回溯并记录路径
- 再从q节点向上回溯，第一个在p路径中的节点就是LCA

递归方案代码示例：

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

3. 二叉树进阶技巧与优化

3.1 Morris遍历算法

Morris遍历是一种空间复杂度为O(1)的二叉树遍历算法，它通过利用叶子节点的空指针来实现无需栈或递归的遍历。

中序Morris遍历的核心思想：

如果当前节点的左子节点为空，访问当前节点并转向右子节点
如果左子节点不为空：
- 找到当前节点在中序遍历下的前驱节点
- 如果前驱节点的右指针为空，将其指向当前节点，然后转向左子节点
- 如果前驱节点的右指针指向当前节点，说明左子树已遍历完，恢复指针，访问当前节点，转向右子节点

def morris_inorder(root): curr = root while curr: if not curr.left: print(curr.val) # 访问节点 curr = curr.right else: # 找到前驱节点 pre = curr.left while pre.right and pre.right != curr: pre = pre.right if not pre.right: pre.right = curr # 建立线索 curr = curr.left else: pre.right = None # 恢复树结构 print(curr.val) # 访问节点 curr = curr.right

3.2 二叉树与动态规划结合

某些二叉树问题可以转化为动态规划思路来解决，特别是涉及最优解或计数类问题。例如LeetCode 96题"不同的二叉搜索树"。

这类问题的典型解决步骤：

定义dp数组含义：dp[i]表示i个节点能组成的BST数量
找出状态转移方程：dp[i] = Σ(dp[j-1] * dp[i-j])，j从1到i
确定初始条件：dp[0] = 1, dp[1] = 1
按顺序计算dp数组

def numTrees(n): dp = [0] * (n + 1) dp[0], dp[1] = 1, 1 for i in range(2, n + 1): for j in range(1, i + 1): dp[i] += dp[j - 1] * dp[i - j] return dp[n]

4. 二叉树实战问题精讲

4.1 二叉树的最大路径和

LeetCode 124题"二叉树中的最大路径和"是一道经典难题。题目要求找到二叉树中任意节点到任意节点的路径，使得路径和最大。

解题关键点：

路径不一定经过根节点
路径至少包含一个节点
需要同时考虑以当前节点为根的子树内部最大路径和
以及当前节点作为路径一部分时能贡献的最大值

解决方案：

使用后序遍历递归处理
对于每个节点，计算其作为路径一部分时的最大贡献值
同时更新全局最大路径和

def maxPathSum(root): max_sum = float('-inf') def max_gain(node): nonlocal max_sum if not node: return 0 left_gain = max(max_gain(node.left), 0) right_gain = max(max_gain(node.right), 0) # 当前节点作为根时的路径和 price_newpath = node.val + left_gain + right_gain max_sum = max(max_sum, price_newpath) # 返回当前节点的最大贡献值 return node.val + max(left_gain, right_gain) max_gain(root) return max_sum

4.2 二叉树的右视图

LeetCode 199题"二叉树的右视图"要求返回从右侧看二叉树时能看到的节点值。这类层级相关问题通常使用广度优先搜索(BFS)更为直观。

解题思路：

使用队列进行层级遍历
记录每层的最后一个节点
也可以使用DFS，优先访问右子树，记录每个深度第一个访问的节点

BFS方案实现：

from collections import deque def rightSideView(root): if not root: return [] queue = deque([root]) res = [] while queue: level_size = len(queue) for i in range(level_size): node = queue.popleft() if i == level_size - 1: res.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return res