剑指 Offer（第2版）面试题 68：树中两个结点的最低公共祖先

剑指 Offer（第2版）面试题 68：树中两个结点的最低公共祖先
- 解法1：递归
- 拓展题：二叉搜索树的最近公共祖先
- - 解法1：两次遍历
  - 解法2：一次遍历

剑指 Offer（第2版）面试题 68：树中两个结点的最低公共祖先

题目来源：88. 树中两个结点的最低公共祖先

题目描述：给出一个二叉树，输入两个树节点，求它们的最低公共祖先。一个树节点的祖先节点包括它本身。

解法1：递归

祖先的定义：若节点 p 在节点 root 的左（右）子树中，或 p=root，则称 root 是 p 的祖先。

最近公共祖先的定义：设节点 root 为节点 p、q 的某公共祖先，若其左子节点 root.left 和右子节点 root.right 都不是 p、q 的公共祖先，则称 root 是“最近的公共祖先”。

根据以上定义，若 root 是 p、q 的最近公共祖先，则只可能为以下情况之一：

p 和 q 在 root 的子树中，且分列 root 的异侧（即分别在左、右子树中）；
p=root，且 qqq 在 root 的左或右子树中；
q=root，且 ppp 在 root 的左或右子树中；

考虑通过递归对二叉树进行先序遍历，当遇到节点 p 或 q 时返回。从底至顶回溯，当节点 p、q 在节点 root 的异侧时，节点 root 即为最近公共祖先，则向上返回 root。

在这里插入图片描述

代码：

/**
 * 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 (root == nullptr)
			return root;
		// p 和 q 其中有一个正好是 root，直接返回 root 就行
		if (root == p || root == q)
			return root;
		// 通过递归，得到左右两棵子树的值
		TreeNode *leftLCA = lowestCommonAncestor(root->left, p, q);
		TreeNode *rightLCA = lowestCommonAncestor(root->right, p, q);
		// p 和 q 分别在 root 的不同子树，直接返回 root 就行
		if (leftLCA && rightLCA)
			return root;
		// p 和 q 在 root 的同一侧，且 root 不等于 p 或者 q 的任何一个，那么就找 p 和 q 在的那一侧子树
		return leftLCA == nullptr ? rightLCA : leftLCA;
	}
};

复杂度分析：

时间复杂度：O(n)，其中 n 是二叉树的节点个数。最差情况下，需要递归遍历树的所有节点。

空间复杂度：O(height)，其中 height 是二叉树的深度。

拓展题：二叉搜索树的最近公共祖先

题目链接：235. 二叉搜索树的最近公共祖先

解法1：两次遍历

分别找到 root 到 p 和 root 到 p 的路径，因为 root 到 p 和 q 的最近公共祖先的路径长度一样，所以比较 path_p[i] 和 path_q[i] 即可，相等就说明找到了 p 和 q 的最近公共祖先。

代码：

// 两次遍历

class Solution
{
public:
    // 主函数
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        TreeNode *ancestor = nullptr;
        vector<TreeNode *> path_p = getPath(root, p);
        vector<TreeNode *> path_q = getPath(root, q);
        for (int i = 0; i < path_p.size() && i < path_q.size(); i++)
        {
            if (path_p[i] == path_q[i])
                ancestor = path_p[i];
            else
                break;
        }
        return ancestor;
    }
    // 辅函数 - 得到从根节点到目标节点的路径
    vector<TreeNode *> getPath(TreeNode *root, TreeNode *target)
    {
        vector<TreeNode *> path;
        TreeNode *node = root;
        while (node != target)
        {
            path.push_back(node);
            if (node->val > target->val)
                node = node->left;
            else
                node = node->right;
        }
        path.push_back(node);
        return path;
    }
};

复杂度分析：

时间复杂度：O(n)，其中 n 是给定的二叉搜索树中的节点个数。

空间复杂度：O(n)，其中 n 是给定的二叉搜索树中的节点个数。我们需要存储根节点到 p 和 q 的路径。

解法2：一次遍历

利用二叉搜索树的特性，只需要一次遍历。

我们从根节点开始遍历：

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

代码：

// 一次遍历

class Solution
{
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        TreeNode *ancestor = root;
        while (1)
        {
            // 如果当前节点的值大于 p 和 q 的值，说明 p 和 q 在当前节点的左子树
            if (ancestor->val > p->val && ancestor->val > q->val)
                ancestor = ancestor->left;
            // 如果当前节点的值小于p和q的值，说明p和q在当前节点的右子树
            else if (ancestor->val < p->val && ancestor->val < q->val)
                ancestor = ancestor->right;
            else // 当前节点就是「分岔点」
                break;
        }
        return ancestor;
    }
};