0235. 二叉搜索树的最近公共祖先 #
- 标签:树
- 难度:简单
题目大意 #
描述:给定一个二叉搜索树的根节点 root
,以及两个指定节点 p
和 q
。
要求:找到该树中两个指定节点的最近公共祖先。
说明:
- 祖先:若节点
p
在节点node
的左子树或右子树中,或者p == node
,则称node
是p
的祖先。 - 最近公共祖先:对于树的两个节点
p
、q
,最近公共祖先表示为一个节点lca_node
,满足lca_node
是p
、q
的祖先且lca_node
的深度尽可能大(一个节点也可以是自己的祖先)。 - 所有节点的值都是唯一的。
p
、q
为不同节点且均存在于给定的二叉搜索树中。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:递归遍历 #
对于节点 p
、节点 q
,最近公共祖先就是从根节点分别到它们路径上的分岔点,也是路径中最后一个相同的节点,现在我们的问题就是求这个分岔点。
我们可以使用递归遍历查找二叉搜索树的最近公共祖先,具体方法如下。
- 从根节点
root
开始遍历。 - 如果当前节点的值大于
p
、q
的值,说明p
和q
应该在当前节点的左子树,因此将当前节点移动到它的左子节点,继续遍历; - 如果当前节点的值小于
p
、q
的值,说明p
和q
应该在当前节点的右子树,因此将当前节点移动到它的右子节点,继续遍历; - 如果当前节点不满足上面两种情况,则说明
p
和q
分别在当前节点的左右子树上,则当前节点就是分岔点,直接返回该节点即可。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。其中 $n$ 是二叉搜索树的节点个数。
- 空间复杂度:$O(1)$。