题目
标题和出处
标题：二叉搜索树的最近公共祖先
难度
3 级
题目描述
要求
给定一个二叉搜索树，找到该树中两个指定结点的最近公共祖先。
最近公共祖先的定义为：两个结点 p \texttt{p} p 和 q \texttt{q} q 的最近公共祖先是满足 p \texttt{p} p 和 q \texttt{q} q 都是其后代的最低的结点 T \texttt{T} T（一个结点也可以是它自己的祖先）。
示例
示例 1：
输入： root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 \texttt{root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8} root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出： 6 \texttt{6} 6
解释：结点 2 \texttt{2} 2 和结点 8 \texttt{8} 8 的最近公共祖先是结点 6 \texttt{6} 6。
示例 2：
输入： root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 \texttt{root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4} root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出： 2 \texttt{2} 2
解释：结点 2 \texttt{2} 2 和结点 4 \texttt{4} 4 的最近公共祖先是结点 2 \texttt{2} 2。因为根据定义最近公共祖先结点可以为结点本身。
示例 3：
输入： root = [2,1], p = 2, q = 1 \texttt{root = [2,1], p = 2, q = 1} root = [2,1], p = 2, q = 1
输出： 2 \texttt{2} 2
数据范围
- 树中结点数目在范围 [2, 10 5 ] \texttt{[2, 10}^\texttt{5}\texttt{]} [2, 105] 内
- -10 9 ≤ Node.val ≤ 10 9 \texttt{-10}^\texttt{9} \le \texttt{Node.val} \le \texttt{10}^\texttt{9} -109≤Node.val≤109
- 所有 Node.val \texttt{Node.val} Node.val 各不相同
- p ≠ q \texttt{p} \ne \texttt{q} p=q
- p \texttt{p} p 和 q \texttt{q} q 均存在于给定的二叉搜索树中
解法一
思路和算法
如果结点 p p p 和 q q q 之间的关系是祖先和后代的关系，则其中的祖先即为最近公共祖先。如果结点 p p p 和 q q q 之间的关系不是祖先和后代的关系，则结点 p p p 和 q q q 分别在最近公共祖先的两个子树中。
对于二叉搜索树中的任意结点，其左子树中的结点值都小于当前结点值，其右子树中的结点值都大于当前结点值。首先比较根结点值和结点 p p p 和 q q q 的结点值，缩小寻找最近公共祖先的范围。
-
如果根结点值比结点 p p p 和 q q q 的结点值都大，则结点 p p p 和 q q q 都在根结点的左子树中，因此根结点的左子结点一定是结点 p p p 和 q q q 的公共祖先，应该在根结点的左子树中寻找最近公共祖先。
-
如果根结点值比结点 p p p 和 q q q 的结点值都小，则结点 p p p 和 q q q 都在根结点的右子树中，因此根结点的右子结点一定是结点 p p p 和 q q q 的公共祖先，应该在根结点的右子树中寻找最近公共祖先。
-
如果根结点值介于结点 p p p 和结点 q q q 的结点值之间（可以等于其中的一个结点值），则根结点的任何一个子结点都不可能是结点 p p p 和 q q q 的公共祖先，因此根结点是结点 p p p 和 q q q 的最近公共祖先。
上述过程是一个递归的过程。递归的终止条件是当前结点值介于结点 p p p 和结点 q q q 的结点值之间，此时当前结点是结点 p p p 和 q q q 的最近公共祖先，返回当前结点。对于其余情况，定位到最近公共祖先所在的子树，对该子树调用递归。
由于结点 p p p 和 q q q 都存在于给定的二叉搜索树中，因此最近公共祖先一定存在。
代码
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int maxVal = Math.max(p.val, q.val);
int minVal = Math.min(p.val, q.val);
if (root.val <= maxVal && root.val >= minVal) {
return root;
}
return root.val > maxVal ? lowestCommonAncestor(root.left, p, q) : lowestCommonAncestor(root.right, p, q);
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是二叉搜索树的结点数。时间复杂度取决于二叉搜索树的高度，最坏情况下二叉搜索树的高度是 O ( n ) O(n) O(n)。
-
空间复杂度： O ( n ) O(n) O(n)，其中 n n n 是二叉搜索树的结点数。空间复杂度主要是递归调用的栈空间，取决于二叉搜索树的高度，最坏情况下二叉搜索树的高度是 O ( n ) O(n) O(n)。
解法二
思路和算法
递归实现可以改成迭代实现。从根结点开始搜索，如果当前结点值结点值比结点 p p p 和 q q q 的结点值都大或者都小，则执行如下操作，直到当前结点值介于结点 p p p 和结点 q q q 的结点值之间。
-
如果当前结点值比结点 p p p 和 q q q 的结点值都大，则结点 p p p 和 q q q 都在当前结点的左子树中，因此将当前结点移动到左子结点。
-
如果当前结点值比结点 p p p 和 q q q 的结点值都小，则结点 p p p 和 q q q 都在当前结点的右子树中，因此将当前结点移动到右子结点。
搜索结束时，当前结点为结点 p p p 和 q q q 的最近公共祖先，返回当前结点。
由于结点 p p p 和 q q q 都存在于给定的二叉搜索树中，因此最近公共祖先一定存在。
代码
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int maxVal = Math.max(p.val, q.val);
int minVal = Math.min(p.val, q.val);
TreeNode node = root;
while (node.val > maxVal || node.val < minVal) {
if (node.val > maxVal) {
node = node.left;
} else {
node = node.right;
}
}
return node;
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是二叉搜索树的结点数。时间复杂度取决于二叉搜索树的高度，最坏情况下二叉搜索树的高度是 O ( n ) O(n) O(n)。
-
空间复杂度： O ( 1 ) O(1) O(1)。