当前位置:网站首页>236. 二叉树的最近公共祖先
236. 二叉树的最近公共祖先
2022-08-03 00:23:00 【ZNineSun】
打卡!!!每日一题
今天给大家带来一道树类型的题目,也是一道比较经典的深度优先遍历的题目
题目描述:236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
题目示例:
题目大概可以分为以下几种情形:
- 如果两个节点中有任意一个是根节点,那么我们就可以直接返回根节点
- 如果两个节点在树的两侧,那么他们最近的公共祖先也只能是根节点
- 最难的情况便是两个节点在树的同一侧
对于p或q是根节点的情况,我们只需判断p或q是否和根节点相等即可
if (p.val == root.val || q.val == root.val) {
return root;
}
判断是否在树的两侧,我们只需划分左右子树即可
int rootIndex = allNodeVal.indexOf(root.val);
int pIndex = allNodeVal.indexOf(p.val);
int qIndex = allNodeVal.indexOf(q.val);
/**2.两个节点在树的两侧**/
if (pIndex < rootIndex && qIndex > rootIndex || pIndex > rootIndex && qIndex < rootIndex) {
return root;
}
两个节点在同一侧的话,我们需要用一个Hash表存储每个节点的所有父节点,然后获取p,q的父节点列表,因为我们需要层数最深的父节点 ,所以我们可以考虑采用中序遍历二叉树,这样的话层数最深的结点就会在链表的前面
public void dfs(TreeNode root) {
if (root == null) return;
if (root.left != null) {
parent.put(root.left.val, root);
dfs(root.left);
}
if (root.right != null) {
parent.put(root.right.val, root);
dfs(root.right);
}
}
完整代码如下:
package com.exercise.leetecode.problem.剑指offer.前中后序遍历;
import com.exercise.leetecode.common.TreeNode;
import java.util.*;
public class 二叉树的最近公共祖先_236 {
Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
List<Integer> allNodeVal = new ArrayList<>();
TreeNode r;//存放根节点
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
/**1.说明其中有一个结点是根节点**/
if (p.val == root.val || q.val == root.val) {
return root;
}
//判断两个节点是否在同一侧
r = root;
dfs_in(root);
root = r;
boolean sig_p = false, sig_q = false;
int rootIndex = allNodeVal.indexOf(root.val);
int pIndex = allNodeVal.indexOf(p.val);
int qIndex = allNodeVal.indexOf(q.val);
/**2.两个节点在树的两侧**/
if (pIndex < rootIndex && qIndex > rootIndex || pIndex > rootIndex && qIndex < rootIndex) {
return root;
}
dfs(root);
List<TreeNode> pParent = new ArrayList<>();
pParent.add(p);
while (p != null) {
p = parent.get(p.val);
pParent.add(p);
}
List<Integer> qParent = new ArrayList<>();
qParent.add(q.val);
while (q != null) {
q = parent.get(q.val);
if (q != null) {
qParent.add(q.val);
}
}
for (TreeNode t : pParent) {
if (qParent.contains(t.val)) {
return t;
}
}
return null;
}
public void dfs_in(TreeNode root) {
if (root == null) {
return;
}
dfs_in(root.left);
allNodeVal.add(root.val);
dfs_in(root.right);
}
public void dfs(TreeNode root) {
if (root == null) return;
if (root.left != null) {
parent.put(root.left.val, root);
dfs(root.left);
}
if (root.right != null) {
parent.put(root.right.val, root);
dfs(root.right);
}
}
}
边栏推荐
猜你喜欢
新公链时代的跨链安全性解决方案
软件测试从业多年,自认为技术不错,裸辞:一晃 ,失业3个月了~
Auto.js special positioning control method cannot perform blocking operations on the ui thread, please use setTimeout instead
线上交流丨稀疏神经网络:实践和理论(青源Talk第23期 汪张扬)
文树勋率长沙市人大常委会主任会议成员莅临麒麟信安调研数字经济发展情况
Day017 封装
【问题征集】向 iPod 之父、iPhone 联合设计者、Google Nest 创始人 Tony Fadell 提问啦
Heartwarming AI Review (1)
vue3的keepAlive缓存组件
鲲鹏devkit开发套件
随机推荐
并查集总结
Oracle 暴跌,倒下了!
麒麟信安邀您抢先看 | openEuler 志高远,开源汇智创未来-开放原子全球开源峰会欧拉分论坛最详细议程出炉
GoLang 使用 goroutine 停止的几种办法
vue3的keepAlive缓存组件
从一文中了解SSRF的各种绕过姿势及攻击思路
牛客网剑指offer刷题练习之链表中环的入口结点
解决错误:Optional int parameter ‘pageSize‘ is present but cannot be translated into a null value due to
flutter 每个要注意的点
Last Common Ancestor (LCA) Study Notes | P3379 【Template】Least Common Ancestor (LCA) Problem Solution
IDEA多线程调试
Understand the next hop address in the network topology in seconds
有奖提问|《新程序员》专访“Apache之父”Brian Behlendorf
担心的事情
MySQL的多表查询(1)
【QT】自定义工程封装成DLL并如何调用(带ui界面的)
几种常见的跨域解决方法
SAP ABAP Gateway Client 里 OData 测试的 PUT, PATCH, MERGE 请求有什么区别
3、Xendesktop更改发布桌面的显示名称(MCS静态桌面)
【深度学习】基于tensorflow的小型物体识别训练(数据集:CIFAR-10)