LeetCode 235. 二叉搜索树的最近公共祖先：利用特性优化查找

LeetCode 235. 二叉搜索树的最近公共祖先：利用特性优化查找

问题描述

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

示例 1：

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

示例 2：

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

示例 3：

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

算法原理

核心思路

二叉搜索树的最近公共祖先问题可以利用二叉搜索树的特性来优化查找过程。二叉搜索树的特性是：

• 左子树中的所有节点值都小于根节点的值
• 右子树中的所有节点值都大于根节点的值
• 左右子树也都是二叉搜索树

基于这个特性，我们可以通过以下方法找到最近公共祖先：

1. 从根节点开始遍历
2. 如果当前节点的值大于 p 和 q 的值，说明 p 和 q 都在左子树中，递归遍历左子树
3. 如果当前节点的值小于 p 和 q 的值，说明 p 和 q 都在右子树中，递归遍历右子树
4. 否则，当前节点就是 p 和 q 的最近公共祖先

复杂度分析

• 时间复杂度：O(h)，其中 h 是二叉搜索树的高度。在最坏情况下，需要遍历到树的叶子节点。
• 空间复杂度：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': # 如果当前节点的值大于 p 和 q 的值，递归遍历左子树 if root.val > p.val and root.val > q.val: return self.lowestCommonAncestor(root.left, p, q) # 如果当前节点的值小于 p 和 q 的值，递归遍历右子树 if root.val < p.val and root.val < q.val: return self.lowestCommonAncestor(root.right, p, q) # 否则，当前节点就是最近公共祖先 return root

迭代实现

# 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': # 迭代遍历 while root: # 如果当前节点的值大于 p 和 q 的值，遍历左子树 if root.val > p.val and root.val > q.val: root = root.left # 如果当前节点的值小于 p 和 q 的值，遍历右子树 elif root.val < p.val and root.val < q.val: root = root.right # 否则，当前节点就是最近公共祖先 else: return root return None

代码解析

递归实现

1. 比较节点值：如果当前节点的值大于 p 和 q 的值，说明 p 和 q 都在左子树中，递归遍历左子树。
2. 比较节点值：如果当前节点的值小于 p 和 q 的值，说明 p 和 q 都在右子树中，递归遍历右子树。
3. 返回结果：否则，当前节点就是 p 和 q 的最近公共祖先。

迭代实现

1. 初始化：从根节点开始遍历。
2. 循环遍历：
   • 如果当前节点的值大于 p 和 q 的值，遍历左子树。
   • 如果当前节点的值小于 p 和 q 的值，遍历右子树。
   • 否则，当前节点就是最近公共祖先，返回当前节点。
3. 返回结果：如果循环结束，返回None。

实战技巧

利用二叉搜索树的特性

• 有序性：二叉搜索树的中序遍历是有序的，利用这一特性可以快速定位节点的位置。
• 递归与迭代：递归实现代码简洁，迭代实现避免了递归栈溢出的问题。

边界条件处理

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

错误分析

常见错误

1. 递归终止条件错误：忘记处理递归的终止条件，导致递归无法终止。
2. 节点值比较错误：在比较节点值时，逻辑判断错误。
3. 迭代循环条件错误：在迭代实现中，循环条件设置错误，导致无限循环。

扩展思考

变种问题

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

应用场景

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

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

个人实践感悟

最近在准备转正答辩，每天被各种算法题和合并冲突吓醒，救命！今天刷到这个经典的二叉搜索树的最近公共祖先问题，突然想到刚实习时第一次写这个题的场景。当时我还不知道利用二叉搜索树的特性，直接用了二叉树的最近公共祖先的解法，被mentor嘲笑了一整天，麻了！

现在再看这个问题，其实关键在于利用二叉搜索树的特性。通过比较节点值的大小，可以快速定位 p 和 q 的位置，从而找到最近公共祖先。这让我意识到，算法的学习真的是一个循序渐进的过程，从一无所知到熟练掌握，需要不断地练习和总结。

最后，分享一个小技巧：在面试中遇到二叉搜索树的问题，首先要想到利用其特性进行优化。二叉搜索树的有序性可以帮助我们快速定位节点的位置，从而提高算法的效率。这就是大佬吗？我也要成为这样的人！

输入输出示例

输入输出示例 1

输入：

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

输出：

6

输入输出示例 2

输入：

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

输出：

2

输入输出示例 3

输入：

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

输出：

2

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