Scott's Blog

学则不固, 知则不惑

0%

算法题:二叉搜索树的最近公共祖先

发表于 更新于 分类于 阅读次数： Valine：

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

二叉搜索树的定义：

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉排序树。

在此题目中，会提供 p, q 2个节点，我们需要确定这两个节点的公共祖先。

首先我们知道，根节点肯定是所有节点的祖先，其次根据二叉搜索树的特性，当我们将 p 和 q 分别与根节点做对比的时候，可以排除掉一半的值，因为左边的节点肯定小于右边的节点，当 p 大于根节点，那我们需要找的那个公共祖先肯定在右半部分子树。

还有一种特殊情况需要考虑，那就是 p 或者 q 于根节点是相等的，这时候公共祖先其实就是根节点了。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        cur = root
        while cur:
            # 如果两个节点都在左边，将当前指针往左边移动
            if p.val < root.val and q.val < root.val:
                cur = cur.left
            # 如果两个节点都在右边，将当前指针往右边移动
            elif p.val > root.val and q.val > root.val:
                cur = cur.right
            # 两种情况都不是，则说明两个节点分叉，当前节点即为结果
            else:
                return cur