题目

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1：

• 输入：root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
• 输出：6
• 解释：节点 2 和节点 8 的最近公共祖先是 6。

示例 2：

• 输入：root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
• 输出：2
• 解释：节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

方法一：一次遍历

思路及解法

整体的遍历过程如下：

• 我们从根节点开始遍历；

• 如果当前节点的值大于 和 的值，说明 和 应该在当前节点的左子树，因此将当前节点移动到它的左子节点；

• 如果当前节点的值小于 和 的值，说明 和 应该在当前节点的右子树，因此将当前节点移动到它的右子节点；

• 如果当前节点的值不满足上述两条要求，那么说明当前节点就是「分岔点」。此时， 和 要么在当前节点的不同的子树中，要么其中一个就是当前节点。

代码

class Solution {
    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
        var ancestor: TreeNode? = root
        while true {
            if (p?.val ?? 0) < (ancestor?.val ?? 0) && (q?.val ?? 0) < (ancestor?.val ?? 0) {
                ancestor = ancestor?.left
            }
            else if (p?.val ?? 0) > (ancestor?.val ?? 0) && (q?.val ?? 0) > (ancestor?.val ?? 0) {
                ancestor = ancestor?.right
            }
            else {
                break
            }
        }
        return ancestor
    }
}

复杂度分析

• 时间复杂度：，其中 是给定的二叉搜索树中的节点个数。分析思路与方法一相同。

• 空间复杂度：。