| 🚀 算法题 🚀 |
🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域优质创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯
| 🚀 算法题 🚀 |
🍔 目录
- 🚩 题目链接
- ⛲ 题目描述
- 🌟 求解思路&实现代码&运行结果
- ⚡ 数组 + 递归
- 🥦 求解思路
- 🥦 实现代码
- 💬 共勉
🚩 题目链接
⛲ 题目描述
给定一个数组来表示二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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 均存在于给定的二叉树中。
🌟 求解思路&实现代码&运行结果
⚡ 数组 + 递归
🥦 求解思路
- 方法参数：
- root：存储二叉树节点值的数组。
- p：需要查找最近公共祖先的第一个节点的值。
- q：需要查找最近公共祖先的第二个节点的值。
- index：当前正在处理的节点在数组中的索引。
- 递归逻辑：
- 结果判断：
- 若左子树和右子树的返回结果都不为 -1，表明当前节点是最近公共祖先，返回当前节点的值。
- 若左子树的返回结果不为 -1，返回左子树的结果。
- 否则返回右子树的结果。
- main 方法：
- 定义数组 root 来表示二叉树，同时指定 p 和 q 的值。
- 从根节点的索引 0 开始调用 lowestCommonAncestor 方法，将结果打印输出。
- 细节注意：
- 使用 2 * i 和 2 * i + 1 作为左右子树索引需要满足数组索引从 1 开始存储的前提条件
- 有了基本的思路，接下来我们就来通过代码来实现一下。
🥦 实现代码
java">public class LowestCommonAncestorInArray {// 查找最近公共祖先的核心方法public static int lowestCommonAncestor(int[] root, int p, int q, int index) {// 如果当前索引超出数组范围，或者当前位置的值为无效值（这里假设 -1 表示无效），返回 -1if (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);}
}
💬 共勉
| 最后，我想和大家分享一句一直激励我的座右铭，希望可以与大家共勉！ |
