小学生都能看懂的题解 | #二叉搜索树的最近公共祖先#

什么是二叉搜索树？

二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树。在BST中，每个节点都有一个值，并且满足以下条件：

• 左边的子树上的所有节点的值都比当前节点小。
• 右边的子树上的所有节点的值都比当前节点大。

什么是最近公共祖先？

最近公共祖先（Lowest Common Ancestor，简称LCA）是指在树中两个节点共享的最近的那个祖先节点。比如，如果节点A和节点B都在节点C的下面，并且C是最靠近A和B的共同节点，那么C就是A和B的最近公共祖先。

如何找到两个节点的最近公共祖先？

我们可以通过比较节点的值来找到两个节点的最近公共祖先。具体步骤如下：

1. 从根节点开始：
1. 我们从树的顶部（根节点）开始查找。
2. 比较节点的值：
1. 如果当前节点的值大于两个目标节点的值，那么最近公共祖先一定在当前节点的左边。
2. 如果当前节点的值小于两个目标节点的值，那么最近公共祖先一定在当前节点的右边。
3. 如果当前节点的值介于两个目标节点的值之间（或者等于其中一个目标节点的值），那么当前节点就是我们要找的最近公共祖先。
3. 重复步骤：
1. 我们不断重复这个过程，直到找到最近公共祖先为止。

示例代码解释：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    // 主方法用来查找最近公共祖先
    public int lowestCommonAncestor(TreeNode root, int p, int q) {
        // 不断更新当前节点
        while (root != null) {
            // 如果当前节点的值大于 p 和 q 的值，LCA 在左子树
            if (root.val > p && root.val > q) {
                root = root.left;
            }
            // 如果当前节点的值小于 p 和 q 的值，LCA 在右子树
            else if (root.val < p && root.val < q) {
                root = root.right;
            }
            // 如果当前节点的值介于 p 和 q 之间（或等于其中之一），当前节点就是 LCA
            else {
                return root.val;
            }
        }
        
        // 如果没有找到，则返回特定值（例如：-1）
        return -1;
    }
}

具体步骤解释：

1. 定义节点类：
1. TreeNode 类包含节点的值 val，以及指向左子树和右子树的引用 left 和 right。
2. 定义查找方法：
1. lowestCommonAncestor 方法接收三个参数，分别是根节点 root 和两个目标节点的值 p 和 q。
3. 循环查找：
1. 从根节点开始，检查当前节点的值。
2. 如果当前节点的值大于 p 和 q 的值，说明最近公共祖先在当前节点的左子树中，更新 root 为 root.left。
3. 如果当前节点的值小于 p 和 q 的值，说明最近公共祖先在当前节点的右子树中，更新 root 为 root.right。
4. 如果当前节点的值介于 p 和 q 的值之间（或等于其中之一），说明当前节点就是最近公共祖先，返回当前节点的值。
4. 如果没有找到：
1. 如果循环结束还没有找到最近公共祖先，返回 -1。

示例：

假设我们有如下二叉搜索树：

      7
     / \
    1  12
   / \  /
  0  4 11
     / \
    3  5

如果我们想找到节点 1 和节点 12 的最近公共祖先，我们按照上面的步骤进行：

1. 从根节点 7 开始。
2. 7 的值大于 1 和 12 的值吗？不是。
3. 7 的值小于 1 和 12 的值吗？不是。
4. 7 的值介于 1 和 12 的值之间，所以 7 就是我们要找的最近公共祖先。

因此，7 就是节点 1 和节点 12 的最近公共祖先。

如果这篇文章对你有帮助，请点个免费的赞👍，让它能帮助更多的人。