文章目录
- 题目
- 标题和出处
- 难度
- 题目描述
- 要求
- 示例
- 数据范围
- 解法一
- 思路和算法
- 代码
- 复杂度分析
- 解法二
- 思路和算法
- 代码
- 复杂度分析
题目
标题和出处
标题:二叉搜索树的最近公共祖先
出处:235. 二叉搜索树的最近公共祖先
难度
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)。