当前位置：首页 > ds >正文

leetcode235.二叉搜索树的最近公共祖先：迭代法利用有序性高效寻根

ds 2025/8/26 0:13:56

一、题目深度解析与BST特性利用

题目描述

给定一棵二叉搜索树（BST），找到树中两个指定节点的最近公共祖先（LCA）。最近公共祖先是指在两个节点的所有祖先中，距离它们最近的共同祖先节点。本题要求：

利用BST的特性优化查找过程
不使用递归，通过迭代方式实现
确保时间复杂度优于普通二叉树的O(n)

BST的核心特性应用

二叉搜索树的重要性质：

左子树所有节点值 < 根节点值
右子树所有节点值 > 根节点值
中序遍历结果为严格递增序列

这些特性使得我们可以通过比较节点值的大小来高效判断公共祖先的位置，避免对整棵树进行遍历。

二、迭代解法的核心实现与逻辑框架

完整迭代代码实现

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {while(true){if(root.val > p.val && root.val > q.val){root = root.left;  // 当前节点值过大，向左子树移动}else if(root.val < p.val && root.val < q.val){root = root.right; // 当前节点值过小，向右子树移动}else{break;  // 找到公共祖先，退出循环}}return root;}
}

核心设计解析：

迭代条件判断：
- root.val > p.val && root.val > q.val：当前节点值同时大于p和q，说明p和q都在左子树
- root.val < p.val && root.val < q.val：当前节点值同时小于p和q，说明p和q都在右子树
- 其他情况：当前节点即为LCA，退出循环
指针移动策略：
- 若当前节点值过大，向左子树移动（root = root.left）
- 若当前节点值过小，向右子树移动（root = root.right）
终止条件：
- 当当前节点值介于p和q之间时，停止迭代
- 包括相等情况（如root.val == p.val或root.val == q.val）

三、核心问题解析：BST特性与迭代逻辑

1. BST特性如何简化LCA查找

关键性质推导：

若p和q都在左子树，则LCA必在左子树
若p和q都在右子树，则LCA必在右子树
若p和q分别在左右子树，则当前节点即为LCA

数学表达式：

设当前节点为root，则：

当root.val > p.val && root.val > q.val时，LCA ∈ root.left
当root.val < p.val && root.val < q.val时，LCA ∈ root.right
否则，LCA = root

2. 迭代逻辑的切入点

迭代条件的三种情况：

情况一：当前节点值同时大于p和q
```
if(root.val > p.val && root.val > q.val)
```
- 处理逻辑：向左子树移动，因为左子树所有节点值更小
- 几何意义：在BST的数值分布中向左搜索
情况二：当前节点值同时小于p和q
```
else if(root.val < p.val && root.val < q.val)
```
- 处理逻辑：向右子树移动，因为右子树所有节点值更大
- 几何意义：在BST的数值分布中向右搜索
情况三：当前节点值介于p和q之间
```
else
```
- 处理逻辑：停止迭代，当前节点即为LCA
- 数学证明：此时p和q分别位于当前节点的左右子树，根据BST定义，当前节点是唯一可能的LCA

四、迭代流程深度模拟：以示例BST为例

示例BST结构：

        6/ \2   8/ \ / \0  4 7  9/ \3  5

目标节点：p=2，q=4
LCA：2

迭代步骤详解：

初始状态：root=6
- 比较：6 > 2 && 6 > 4 → 条件成立
- 操作：root = root.left → root=2
第二次迭代：root=2
- 比较：2 > 2 && 2 > 4 → 条件不成立
- 比较：2 < 2 && 2 < 4 → 条件不成立
- 结论：当前节点2即为LCA，退出循环
返回结果：root=2

五、算法复杂度分析

1. 时间复杂度

O(h)：h为树的高度
- 平衡BST：h=logn，时间复杂度O(logn)
- 最坏情况（退化为链表）：h=n，时间复杂度O(n)

2. 空间复杂度

O(1)：仅需常数级额外空间
迭代过程中仅使用指针变量，无递归栈空间开销

3. 与普通二叉树解法对比

方法	时间复杂度	空间复杂度	适用场景
BST迭代法	O(h)	O(1)	二叉搜索树
普通二叉树递归	O(n)	O(h)	任意二叉树

六、核心技术点总结：迭代法的三大优势

1. BST有序性的充分利用

路径压缩：每次迭代排除一半子树，直接定位可能的祖先节点
避免回溯：无需遍历整棵树，仅沿一条路径向下搜索

2. 迭代与递归的对比

空间优化：递归解法需O(h)栈空间，迭代法降为O(1)
代码简洁：迭代逻辑更直观，避免递归可能的栈溢出风险

3. 终止条件的严谨性

数学边界：覆盖所有可能的节点值关系
相等处理：当root.val等于p或q时，正确终止迭代

七、常见误区与优化建议

1. 错误的条件判断

误区：使用root.val > p.val || root.val > q.val作为向左条件

// 错误示例
if(root.val > p.val || root.val > q.val) {root = root.left;
}

正确逻辑：必须同时大于两者，因为只要有一个值在右子树，就不能向左

2. 空指针处理

边界检查：虽然题目保证p和q存在于树中，但实际工程中应添加空指针判断
```
if(root == null) return null; // 处理空树情况
```

3. 优化建议：递归实现

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root.val > p.val && root.val > q.val) {return lowestCommonAncestor(root.left, p, q);}if(root.val < p.val && root.val < q.val) {return lowestCommonAncestor(root.right, p, q);}return root;
}