当前位置:网站首页>Sword finger offer 68 - ii The nearest common ancestor of binary tree
Sword finger offer 68 - ii The nearest common ancestor of binary tree
2022-07-04 22:45:00 【LuZhouShiLi】
The finger of the sword Offer 68 - II. The nearest common ancestor of a binary tree
subject
Given a binary tree , Find the nearest common ancestor of the two specified nodes in the tree . In Baidu Encyclopedia, the most recent definition of public ancestor is :“ For a tree T Two nodes of p、q, Recently, the common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible ( A node can also be its own ancestor ).”
Ideas
- If P and Q All are root Left and right nodes of , that root It's the nearest public ancestor we're looking for
- If P and Q All are root The left node , Then the return lowestCommonAncestor(root.left,p,q)
- If P and Q All are root The right of the node , Then the return lowestCommonAncestor(root.right,p,q)
Boundary conditions :
- If root = null That means we can't find , If root = p perhaps root = q, return root
- If the left tree is not found , Recursive functions return null, prove p and q They are all tested at the same time , Then look in the right subtree
- If the right subtree is not found , Recursive functions return null, prove p and q They are all tested at the same time , Then look in the left subtree
Code
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q)
{
return root;
}
TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
if(leftNode == null)
{
return rightNode;
}
if(rightNode == null)
{
return leftNode;
}
return root;
}
}
边栏推荐
- 质量体系建设之路的分分合合
- String类中的常用方法
- 剑指 Offer 65. 不用加减乘除做加法
- Unity修仙手游 | lua动态滑动功能(3种源码具体实现)
- POM in idea XML dependency cannot be imported
- PHP short video source code, thumb animation will float when you like it
- 攻防世界 MISC 进阶区 hit-the-core
- LOGO特训营 第五节 字体结构与设计常用技法
- 业务太忙,真的是没时间搞自动化理由吗?
- La prospérité est épuisée, les choses sont bonnes et mauvaises: Où puis - je aller pour un chef de station personnel?
猜你喜欢
Unity vscode emmylua configuration error resolution
The sandbox has reached a cooperation with digital Hollywood to accelerate the economic development of creators through human resource development
Attack and defense world misc advanced area ditf
Hit the core in the advanced area of misc in the attack and defense world
Advanced area of attack and defense world misc 3-11
攻防世界 MISC 進階區 Erik-Baleog-and-Olaf
Breakpoint debugging under vs2019 c release
Google Earth Engine(GEE)——Tasks升级,实现RUN ALL可以一键下载任务类型中的所有影像
Attack and defense world misc advanced grace-50
Detailed explanation of heap sort code
随机推荐
Taobao commodity review API interface (item_review get Taobao commodity review API interface), tmall commodity review API interface
Tla+ introductory tutorial (1): introduction to formal methods
Advanced area a of attack and defense world misc Masters_ good_ idea
【OpenGL】笔记二十九、抗锯齿(MSAA)
SPSS installation and activation tutorial (including network disk link)
Deployment of JVM sandbox repeater
Sobel filter
UML图记忆技巧
Postgresqlql advanced skills pivot table
More than 30 institutions jointly launched the digital collection industry initiative. How will it move forward in the future?
SPSS安装激活教程(包含网盘链接)
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
Naacl-22 | introduce the setting of migration learning on the prompt based text generation task
LOGO特训营 第一节 鉴别Logo与Logo设计思路
Google Earth Engine(GEE)——Tasks升级,实现RUN ALL可以一键下载任务类型中的所有影像
Introducing QA into the software development lifecycle is the best practice that engineers should follow
共创软硬件协同生态:Graphcore IPU与百度飞桨的“联合提交”亮相MLPerf
Attack and defense world misc advanced grace-50
微服务--开篇
[the 2023 autumn recruitment of MIHA tour] open [the only exclusive internal push code of school recruitment eytuc]