当前位置:网站首页>leetcode刷题:二叉树24(二叉树的最近公共祖先)
leetcode刷题:二叉树24(二叉树的最近公共祖先)
2022-07-07 10:30:00 【涛涛英语学不进去】
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 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。因为根据定义最近公共祖先节点可以为节点本身。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉树中。
这题乍一看其实不难,就是找到这两个结点的路径,然后比较路径的上的值,找到最后一个相等的结点。
递归遍历,如果两个结点都找到,则停止递归。注意递归时要判断是不是单分支结点,不能用叶子结点为null作为终止条件,否则连删两次走过的路径,就结点缺失了,路径跳结点了。要判断,最后一个个删重复路径。
最后就是遍历的时候,这个卡我好久,可能是刷题刷迷糊了,类似 3 5 和 3 5 4 2 这样,找到最后一个公共元素,我做了半小时,无语,用指针法。
不能做了,停一停,散散步去。
package com.programmercarl.tree;
import com.programmercarl.util.GenerateTreeNode;
import java.util.*;
/** * @ClassName LowestCommonAncestor * @Descriotion TODO * @Author nitaotao * @Date 2022/7/6 10:12 * @Version 1.0 * https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/ * 236. 二叉树的最近公共祖先 **/
public class LowestCommonAncestor {
/** * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 * 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x, * 满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” * 来源:力扣(LeetCode) * 链接:https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree * 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 * * @param root * @param p * @param q * @return */
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
/** * 思路清晰: * 找到两个结点的路径 * 路径值比较,当值不相等了,返回上一个路径值 */
this.p = p;
this.q = q;
traversal(root);
int size = Math.min(pPathNode.size(), qPathNode.size());
//指向公共元素
TreeNode result = pPathNode.get(0);
for (int i = 1; i < size; i++) {
if (pPathNode.get(i).val == qPathNode.get(i).val) {
result = pPathNode.get(i);
}
}
// pPathNode.stream().forEach((item) -> System.out.print(item.val));
// System.out.println();
// qPathNode.stream().forEach((item) -> System.out.print(item.val));
// System.out.println();
return result;
}
boolean isFindPandQ = false;
TreeNode p;
TreeNode q;
List<TreeNode> pPathNode = new ArrayList<TreeNode>();
List<TreeNode> qPathNode = new ArrayList<TreeNode>();
List<TreeNode> curPathNode = new ArrayList();
public void traversal(TreeNode root) {
if (isFindPandQ) {
//发现完毕,停止递归
return;
}
curPathNode.add(root);
if (root.val == p.val) {
pPathNode = new ArrayList<>(curPathNode);
//当两个都找到时停止递归
isFindPandQ = pPathNode.size() > 0 && qPathNode.size() > 0;
}
if (root.val == q.val) {
qPathNode = new ArrayList<>(curPathNode);
//当两个都找到时停止递归
isFindPandQ = pPathNode.size() > 0 && qPathNode.size() > 0;
}
//分开讨论两种情况,防止叶子结点删除两次最后位置
if (root.left != null) {
traversal(root.left);
}
if (root.right != null) {
traversal(root.right);
}
curPathNode.remove(curPathNode.size() - 1);
}
public static void main(String[] args) {
System.out.println(new LowestCommonAncestor().lowestCommonAncestor(GenerateTreeNode.generateTreeNode("[3,5,1,6,2,0,8,null,null,7,4]"), new TreeNode(5), new TreeNode(4)).val);
System.out.println(new LowestCommonAncestor().lowestCommonAncestor(GenerateTreeNode.generateTreeNode("[3,5,1,6,2,0,8,null,null,7,4]"), new TreeNode(5), new TreeNode(1)).val);
}
}
边栏推荐
- On valuation model (II): PE index II - PE band
- "Series after reading" my God! It's so simple to understand throttling and anti shake~
- 平安证券手机行开户安全吗?
- Processing strategy of message queue message loss and repeated message sending
- 让数字管理好库存
- How much does it cost to develop a small program mall?
- (待会删)yyds,付费搞来的学术资源,请低调使用!
- 【统计学习方法】学习笔记——第四章:朴素贝叶斯法
- 【统计学习方法】学习笔记——逻辑斯谛回归和最大熵模型
- 金融数据获取(三)当爬虫遇上要鼠标滚轮滚动才会刷新数据的网页(保姆级教程)
猜你喜欢
[play RT thread] RT thread Studio - key control motor forward and reverse rotation, buzzer
<No. 9> 1805. Number of different integers in the string (simple)
盘点JS判断空对象的几大方法
Processing strategy of message queue message loss and repeated message sending
关于 Web Content-Security-Policy Directive 通过 meta 元素指定的一些测试用例
Hi3516全系统类型烧录教程
EPP+DIS学习之路(2)——Blink!闪烁!
Epp+dis learning path (1) -- Hello world!
跨域问题解决方案
(to be deleted later) yyds, paid academic resources, please keep a low profile!
随机推荐
Inverted index of ES underlying principle
Using stack to convert binary to decimal
The left-hand side of an assignment expression may not be an optional property access. ts(2779)
对话PPIO联合创始人王闻宇:整合边缘算力资源,开拓更多音视频服务场景
Epp+dis learning path (1) -- Hello world!
What is an esp/msr partition and how to create an esp/msr partition
Let digital manage inventory
How to understand the clothing industry chain and supply chain
H3C HCl MPLS layer 2 dedicated line experiment
@What happens if bean and @component are used on the same class?
What is a LAN domain name? How to parse?
Epp+dis learning road (2) -- blink! twinkle!
ps链接图层的使用方法和快捷键,ps图层链接怎么做的
《看完就懂系列》天哪!搞懂节流与防抖竟简单如斯~
EPP+DIS学习之路(1)——Hello world!
Utiliser la pile pour convertir le binaire en décimal
wallys/Qualcomm IPQ8072A networking SBC supports dual 10GbE, WiFi 6
【深度学习】图像多标签分类任务,百度PaddleClas
让数字管理好库存
About sqli lab less-15 using or instead of and parsing