LeetCode 236. 二叉树的最近公共祖先：深度优先搜索的应用

LeetCode 236. 二叉树的最近公共祖先：深度优先搜索的应用

问题描述

给定一个二叉树，找到该树中两个指定节点的最近公共祖先。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5

示例 3：

输入：root = [1,2], p = 1, q = 2 输出：1

算法原理

核心思路

二叉树的最近公共祖先问题可以通过深度优先搜索（DFS）来解决，其核心思想是：

1. 从根节点开始，递归地遍历左右子树
2. 如果当前节点是 p 或 q，返回当前节点
3. 递归地在左子树和右子树中查找 p 和 q
4. 如果左子树和右子树都找到了 p 和 q，那么当前节点就是最近公共祖先
5. 如果只有左子树找到了 p 或 q，返回左子树的结果
6. 如果只有右子树找到了 p 或 q，返回右子树的结果

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点恰好被访问一次。
• 空间复杂度：O(h)，其中 h 是二叉树的高度。递归调用栈的深度最大为 h。

代码实现

# Definition for a binary tree node. class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': # 如果根节点为空，返回 None if not root: return None # 如果当前节点是 p 或 q，返回当前节点 if root == p or root == q: return root # 递归地在左子树和右子树中查找 p 和 q left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) # 如果左子树和右子树都找到了 p 和 q，那么当前节点就是最近公共祖先 if left and right: return root # 如果只有左子树找到了 p 或 q，返回左子树的结果 if left: return left # 如果只有右子树找到了 p 或 q，返回右子树的结果 return right

代码解析

1. 边界处理：如果根节点为None，返回None。
2. 节点检查：如果当前节点是 p 或 q，返回当前节点。
3. 递归查找：递归地在左子树和右子树中查找 p 和 q。
4. 结果判断：
   • 如果左子树和右子树都找到了 p 和 q，那么当前节点就是最近公共祖先。
   • 如果只有左子树找到了 p 或 q，返回左子树的结果。
   • 如果只有右子树找到了 p 或 q，返回右子树的结果。

实战技巧

递归思想

• 自底向上：从叶子节点开始，向上查找 p 和 q 的最近公共祖先。
• 状态传递：通过返回值传递查找状态，左子树和右子树的查找结果会传递给父节点。

边界条件处理

• 空树：如果树为空，返回None。
• 节点在根节点：如果其中一个节点是根节点，那么根节点就是最近公共祖先。

错误分析

常见错误

1. 递归终止条件错误：忘记处理节点为None的情况，导致递归无法终止。
2. 节点比较错误：使用节点值而不是节点引用进行比较，导致错误。
3. 逻辑判断错误：在处理左子树和右子树的查找结果时，逻辑判断错误。

扩展思考

变种问题

1. 二叉搜索树的最近公共祖先：利用二叉搜索树的特性，优化查找过程。
2. N 叉树的最近公共祖先：将二叉树扩展为 N 叉树，查找最近公共祖先。
3. 多个节点的最近公共祖先：查找多个节点的最近公共祖先。

应用场景

最近公共祖先问题在以下场景中有着广泛的应用：

• 树的操作：在树结构中查找节点之间的关系。
• 基因alogy：在家族树中查找共同祖先。
• 网络分析：在网络拓扑中查找节点之间的关系。

个人实践感悟

最近在准备转正答辩，每天被各种算法题和合并冲突吓醒，救命！今天刷到这个经典的最近公共祖先问题，突然想到刚实习时第一次写这个题的场景。当时我还不知道递归的正确逻辑，结果代码在测试用例 [3,5,1,6,2,0,8,null,null,7,4] 上失败了，被mentor嘲笑了一整天，麻了！

现在再看这个问题，其实关键在于正确的递归逻辑。需要从叶子节点开始，向上查找 p 和 q 的最近公共祖先。当左子树和右子树都找到了 p 和 q 时，当前节点就是最近公共祖先。这让我意识到，算法的学习真的是一个循序渐进的过程，从一无所知到熟练掌握，需要不断地练习和总结。

最后，分享一个小技巧：在面试中遇到最近公共祖先问题，首先要想到递归实现，同时要注意正确的递归逻辑和边界条件处理。如果是二叉搜索树，可以利用其特性进行优化。这就是大佬吗？我也要成为这样的人！

输入输出示例

输入输出示例 1

输入：

root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

输出：

3

输入输出示例 2

输入：

root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

输出：

5

输入输出示例 3

输入：

root = [1,2], p = 1, q = 2

输出：

1

结语：二叉树的最近公共祖先问题是树算法中的经典问题，掌握它不仅有助于解决相关的LeetCode问题，也能帮助我们更好地理解深度优先搜索的思想。希望这篇文章对大家有所帮助，祝大家刷题愉快！