剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

题目描述

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

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

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

示例 1:

1
2
3

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

示例 2:

1
2
3

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

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

注意：本题与主站 235 题相同：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

算法 1

(递归) $O(h)$

这道题目完全可以使用查找二叉树的最近公共祖先的方法去做，但是这种做法的时间复杂度是 $O(n)$ 的，需要遍历整棵二叉树。对于二叉搜索树要充分利用它的有序特性，可以将时间复杂度优化为 $O(h)$。

由于二叉搜索树的有序性，从上往下遍历会比较方便，左边的都比根节点小，右边的都比根节点大。

递归三部曲：

递归函数的含义：返回以 $root$ 为根节点的包含 $p$ 和 $q$ 的最近公共祖先，如果只包含一个就返回一个。
递归出口条件：如果当前节点为空，返回 NULL，但题目已知肯定存在答案，从上往下遍历的过程中不可能走到空节点，所以可以没有递归出口条件。
单层递归逻辑：
- 如果 $p$ 的值比 $q$ 大，为了方便操作，首先交换一下两个节点的值，保证 $p$ 的值小于 $q$ 的值。
- 如果当前节点的值大于等于 $p$ 的值且小于等于 $q$ 的值，那么当前节点就是 $p$ 和 $q$ 的最近公共祖先。
- 如果当前节点的值大于等于 $p$ 的值和 $q$ 的值，说明答案一定在左子树中，所以递归搜索左子树。否则如果当前节点的值小于等于 $p$ 的值和 $q$ 的值，说明答案一定在右子树中，所以递归搜索右子树。

时间复杂度

由于二叉搜索树的有序性，答案要么在左边要么在右边，最坏情况下只需遍历从头节点到叶子节点的一条链，所以时间复杂度为 $O(h)$，$h$ 为二叉搜索树的高度。

空间复杂度

$O(n)$

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (p->val > q->val) swap(p, q);
        // 这里要加等于，因为当前节点可能是 p 或者 q，即 p 可能是 q 的祖先或者 q 是 p 的祖先
        if (p->val <= root->val && root->val <= q->val) return root;
        if (p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left, p, q);
        return lowestCommonAncestor(root->right, p, q);
    }
};

算法 2

(迭代) $O(h)$

由于二叉搜索树的有序性，从根节点开始往下搜索，一定能找到答案。思路和递归是一样的。

时间复杂度

空间复杂度

$O(1)$

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while (root) {
            if (root->val > p->val && root->val > q->val) root = root->left;
            else if (root->val < p->val && root->val < q->val) root = root->right;
            // 不管 p 和 q 谁大，root 都是它们的最近公共祖先
            else return root;
        }
        return NULL;
    }
};