【LeetCode: 面试变体: 236. 二叉树的最近公共祖先 + 数组 + 递归】

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域优质创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯

🚩 题目链接

• 面试变体: 236. 二叉树的最近公共祖先 + 数组 + 递归

⛲ 题目描述

给定一个数组来表示二叉树, 找到该树中两个指定节点的最近公共祖先。

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

示例 1：

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

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

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

🌟 求解思路&实现代码&运行结果

⚡ 数组 + 递归

🥦 求解思路

1. 方法参数：
   • root：存储二叉树节点值的数组。
   • p：需要查找最近公共祖先的第一个节点的值。
   • q：需要查找最近公共祖先的第二个节点的值。
   • index：当前正在处理的节点在数组中的索引。
2. 递归逻辑：
   • 边界条件：当 index 超出数组范围或者当前位置的值为 -1（代表无效节点）时，返回 -1。
   • 节点匹配：若当前节点的值等于 p 或者 q，直接返回该节点的值。
   • 递归调用：分别对左子节点（索引为 2 * index + 1）和右子节点（索引为 2 * index + 2）进行递归调用。
3. 结果判断：
   • 若左子树和右子树的返回结果都不为 -1，表明当前节点是最近公共祖先，返回当前节点的值。
   • 若左子树的返回结果不为 -1，返回左子树的结果。
   • 否则返回右子树的结果。
4. main 方法：
   • 定义数组 root 来表示二叉树，同时指定 p 和 q 的值。
   • 从根节点的索引 0 开始调用 lowestCommonAncestor 方法，将结果打印输出。
5. 细节注意：
   • 使用 2 * i 和 2 * i + 1 作为左右子树索引需要满足数组索引从 1 开始存储的前提条件
6. 有了基本的思路，接下来我们就来通过代码来实现一下。

🥦 实现代码

public class LowestCommonAncestorInArray {

    // 查找最近公共祖先的核心方法
    public static int lowestCommonAncestor(int[] root, int p, int q, int index) {
        // 如果当前索引超出数组范围，或者当前位置的值为无效值（这里假设 -1 表示无效），返回 -1
        if (index >= root.length || root[index] == -1) {
            return -1;
        }
        // 如果当前节点的值等于 p 或者 q，直接返回当前节点的值
        if (root[index] == p || root[index] == q) {
            return root[index];
        }
        // 递归查找左子树中 p 和 q 的最近公共祖先
        int left = lowestCommonAncestor(root, p, q, 2 * index);
        // 递归查找右子树中 p 和 q 的最近公共祖先
        int right = lowestCommonAncestor(root, p, q, 2 * index + 1);

        // 如果左子树和右子树都找到了非 -1 的结果，说明当前节点就是最近公共祖先
        if (left != -1 && right != -1) {
            return root[index];
        }
        // 若左子树找到了结果，返回左子树的结果
        if (left != -1) {
            return left;
        }
        // 否则返回右子树的结果
        return right;
    }

    public static void main(String[] args) {
        int[] root = {3, 5, 1, 6, 2, 0, 8, -1, -1, 7, 4};
        int p = 5;
        int q = 1;
        // 从根节点索引 0 开始调用查找方法
        int result = lowestCommonAncestor(root, p, q, 1);
        System.out.println("最近公共祖先的值是: " + result);
    }
}

💬 共勉