小学生都懂题解 | #在二叉树中找到两个节点的最近公共祖先#

问题描述

我们需要在一个非空的二叉树中找到两个节点 o1 和 o2 的最近公共祖先节点。这里的“最近公共祖先”指的是离这两个节点最近的共同的祖先节点。

解决方案

我们可以用一种简单的方法来解决这个问题，通过递归地查找树中的节点。下面是详细的步骤：

1. 定义方法：
1. 我们定义一个方法 lowestCommonAncestor，它接收三个参数：二叉树的根节点 root，以及两个节点的值 o1 和 o2。
2. 基本情况：
1. 如果当前节点（也就是根节点）是 null（即不存在），那么返回 -1（表示没有找到公共祖先）。
2. 如果当前节点的值正好是 o1 或 o2 中的一个，那么当前节点可能是其中一个节点的公共祖先。
3. 递归查找：
1. 我们从当前节点出发，分别递归地查找左子树和右子树。
2. 如果在左子树中找到了一个公共祖先，返回这个公共祖先的值。
3. 如果在右子树中找到了一个公共祖先，返回这个公共祖先的值。
4. 组合结果：
1. 如果在左子树和右子树中都找到了节点（即两个递归结果都不为空），那么当前节点就是 o1 和 o2 的最近公共祖先。
2. 如果只在左子树中找到了一个节点，那么返回左子树的结果。
3. 如果只在右子树中找到了一个节点，那么返回右子树的结果。
4. 如果左右子树都没有找到节点，那么返回 -1。

示例代码解释

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

public class Solution {
    // 主方法用来查找最近公共祖先
    public int lowestCommonAncestor(TreeNode root, int o1, int o2) {
        if (root == null) {
            return -1; // 基本情况：如果根节点为空，返回-1
        }

        // 如果当前节点的值等于 o1 或 o2，返回当前节点的值
        if (root.val == o1 || root.val == o2) {
            return root.val;
        }

        // 递归地在左子树中查找
        int left = lowestCommonAncestor(root.left, o1, o2);
        // 递归地在右子树中查找
        int right = lowestCommonAncestor(root.right, o1, o2);

        // 如果左右子树的递归结果都不为空，那么当前节点就是最近公共祖先
        if (left != -1 && right != -1) {
            return root.val;
        }

        // 如果只有左子树的递归结果不为空，那么左子树的递归结果就是最近公共祖先
        if (left != -1) {
            return left;
        }

        // 如果只有右子树的递归结果不为空，那么右子树的递归结果就是最近公共祖先
        if (right != -1) {
            return right;
        }

        // 如果左右子树的递归结果都为空，说明没有找到节点 o1 或 o2
        return -1;
    }
}

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