题目

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

百度百科中最近公共祖先的定义为：“对于有根树 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, 因为根据定义最近公共祖先节点可以为节点本身。

方法一：一次遍历

思路及解法

整体的遍历过程如下：

我们从根节点开始遍历；
如果当前节点的值大于 $p$ 和 $q$ 的值，说明 $p$ 和 $q$ 应该在当前节点的左子树，因此将当前节点移动到它的左子节点；
如果当前节点的值小于 $p$ 和 $q$ 的值，说明 $p$ 和 $q$ 应该在当前节点的右子树，因此将当前节点移动到它的右子节点；
如果当前节点的值不满足上述两条要求，那么说明当前节点就是「分岔点」。此时， $p$ 和 $q$ 要么在当前节点的不同的子树中，要么其中一个就是当前节点。

代码

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
    }
}