leetcode 力扣 236 二叉树的最近公共祖先题解 算法题.docx
- 文档编号:5957400
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:15
- 大小:25.28KB
leetcode 力扣 236 二叉树的最近公共祖先题解 算法题.docx
《leetcode 力扣 236 二叉树的最近公共祖先题解 算法题.docx》由会员分享,可在线阅读,更多相关《leetcode 力扣 236 二叉树的最近公共祖先题解 算法题.docx(15页珍藏版)》请在冰点文库上搜索。
leetcode力扣236二叉树的最近公共祖先题解算法题
题目:
二叉树的最近公共祖先
给定一个二叉树,找到该树中两个指定节点的最近公共祖先。
XX百科中最近公共祖先的定义为:
“对于有根树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均存在于给定的二叉树中。
语言:
C++
classSolution{
public:
TreeNode*ans;
booldfs(TreeNode*root,TreeNode*p,TreeNode*q){
if(root==nullptr)returnfalse;
boollson=dfs(root->left,p,q);
boolrson=dfs(root->right,p,q);
if((lson&&rson)||((root->val==p->val||root->val==q->val)&&(lson||rson))){
ans=root;
}
returnlson||rson||(root->val==p->val||root->val==q->val);
}
TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){
dfs(root,p,q);
returnans;
}
};
语言:
C++
classSolution{
public:
unordered_map
unordered_map
voiddfs(TreeNode*root){
if(root->left!
=nullptr){
fa[root->left->val]=root;
dfs(root->left);
}
if(root->right!
=nullptr){
fa[root->right->val]=root;
dfs(root->right);
}
}
TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){
fa[root->val]=nullptr;
dfs(root);
while(p!
=nullptr){
vis[p->val]=true;
p=fa[p->val];
}
while(q!
=nullptr){
if(vis[q->val])returnq;
q=fa[q->val];
}
returnnullptr;
}
};
语言:
C++
classSolution{
public:
TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){
if(root==nullptr||root==p||root==q)returnroot;
TreeNode*left=lowestCommonAncestor(root->left,p,q);
TreeNode*right=lowestCommonAncestor(root->right,p,q);
if(left==nullptr)returnright;
if(right==nullptr)returnleft;
returnroot;
}
};
语言:
JavaScript
varlowestCommonAncestor=function(root,p,q){
letans;
constdfs=(root,p,q)=>{
if(root===null)returnfalse;
constlson=dfs(root.left,p,q);
constrson=dfs(root.right,p,q);
if((lson&&rson)||((root.val===p.val||root.val===q.val)&&(lson||rson))){
ans=root;
}
returnlson||rson||(root.val===p.val||root.val===q.val);
}
dfs(root,p,q);
returnans;
};
语言:
Java
classSolution{
privateTreeNodeans;
publicSolution(){
this.ans=null;
}
privatebooleandfs(TreeNoderoot,TreeNodep,TreeNodeq){
if(root==null)returnfalse;
booleanlson=dfs(root.left,p,q);
booleanrson=dfs(root.right,p,q);
if((lson&&rson)||((root.val==p.val||root.val==q.val)&&(lson||rson))){
ans=root;
}
returnlson||rson||(root.val==p.val||root.val==q.val);
}
publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){
this.dfs(root,p,q);
returnthis.ans;
}
}
语言:
Java
classSolution{
Map
Set
publicvoiddfs(TreeNoderoot){
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);
}
}
publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){
dfs(root);
while(p!
=null){
visited.add(p.val);
p=parent.get(p.val);
}
while(q!
=null){
if(visited.contains(q.val)){
returnq;
}
q=parent.get(q.val);
}
returnnull;
}
}
语言:
Java
classSolution{
publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){
if(root==null||root==p||root==q)returnroot;
TreeNodeleft=lowestCommonAncestor(root.left,p,q);
TreeNoderight=lowestCommonAncestor(root.right,p,q);
if(left==null)returnright;
if(right==null)returnleft;
returnroot;
}
}
语言:
golang
funclowestCommonAncestor(root,p,q*TreeNode)*TreeNode{
ifroot==nil{
returnnil
}
ifroot.Val==p.Val||root.Val==q.Val{
returnroot
}
left:
=lowestCommonAncestor(root.Left,p,q)
right:
=lowestCommonAncestor(root.Right,p,q)
ifleft!
=nil&&right!
=nil{
returnroot
}
ifleft==nil{
returnright
}
returnleft
}
语言:
golang
funclowestCommonAncestor(root,p,q*TreeNode)*TreeNode{
parent:
=map[int]*TreeNode{}
visited:
=map[int]bool{}
vardfsfunc(*TreeNode)
dfs=func(r*TreeNode){
ifr==nil{
return
}
ifr.Left!
=nil{
parent[r.Left.Val]=r
dfs(r.Left)
}
ifr.Right!
=nil{
parent[r.Right.Val]=r
dfs(r.Right)
}
}
dfs(root)
forp!
=nil{
visited[p.Val]=true
p=parent[p.Val]
}
forq!
=nil{
ifvisited[q.Val]{
returnq
}
q=parent[q.Val]
}
returnnil
}
语言:
golang
/**
*Definitionforabinarytreenode.
*typeTreeNodestruct{
*Valint
*Left*TreeNode
*Right*TreeNode
*}
*/
funclowestCommonAncestor(root,p,q*TreeNode)*TreeNode{
ifroot==nil{
returnnil
}
ifroot==p||root==q{
returnroot
}
left:
=lowestCommonAncestor(root.Left,p,q)
right:
=lowestCommonAncestor(root.Right,p,q)
ifleft!
=nil&&right!
=nil{
returnroot
}
ifleft!
=nil{
returnleft
}
returnright
}
语言:
Python
classSolution:
deflowestCommonAncestor(self,root:
TreeNode,p:
TreeNode,q:
TreeNode)->TreeNode:
ifnotrootorroot==porroot==q:
returnroot
left=self.lowestCommonAncestor(root.left,p,q)
right=self.lowestCommonAncestor(root.right,p,q)
ifnotleft:
returnright
ifnotright:
returnleft
returnroot
语言:
Python
classSolution:
deflowestCommonAncestor(self,root:
TreeNode,p:
TreeNode,q:
TreeNode)->TreeNode:
ifnotrootorroot==porroot==q:
returnroot
left=self.lowestCommonAncestor(root.left,p,q)
right=self.lowestCommonAncestor(root.right,p,q)
ifnotleftandnotright:
return#1.
ifnotleft:
returnright#3.
ifnotright:
returnleft#4.
returnroot#2.ifleftandright:
语言:
php
/**
*Definitionforabinarytreenode.
*classTreeNode{
*public$val=null;
*public$left=null;
*public$right=null;
*function__construct($value){$this->val=$value;}
*}
*/
classSolution{
/**
*@paramTreeNode$root
*@paramTreeNode$p
*@paramTreeNode$q
*@returnTreeNode
*/
functionlowestCommonAncestor($root,$p,$q){
$pPath=$this->buildPath($root,$p);//root到p的路径
$qPath=$this->buildPath($root,$q);//root到q的路径
$res=[];
while(!
empty($pPath[0])&&!
empty($qPath[0])){//循环求所有公共祖先
$a=array_pop($pPath[0]);
$b=array_pop($qPath[0]);
if($a->val==$b->val)
$res[]=$a;
}
returnarray_pop($res);//最后一个就是最近的公共祖先
}
//求到某一点的路径
functionbuildPath($root,$p){//深度优先遍历
if($root==null)//递归终止
return[];
if($root->val==$p->val)//递归终止
return[[$p]];
$lPath=$this->buildPath($root->left,$p);//递归左子树
foreach($lPathas$item){//处理返回结果
array_push($item,$root);
return[$item];
}
$rPath=$this->buildPath($root->right,$p);//递归右子树
foreach($rPathas$item){//处理返回结果
array_push($item,$root);
return[$item];
}
}
}
语言:
php
/**
*Definitionforabinarytreenode.
*classTreeNode{
*public$val=null;
*public$left=null;
*public$right=null;
*function__construct($value){$this->val=$value;}
*}
*/
classSolution{
/**
*@paramTreeNode$root
*@paramTreeNode$p
*@paramTreeNode$q
*@returnTreeNode
*/
functionlowestCommonAncestor($root,$p,$q){//深度优先遍历
if($root==null){//递归结束
returnnull;
}
if($root===$p||$root===$q){//递归结束
return$root;
}
$left=$this->lowestCommonAncestor($root->left,$p,$q);//递归
$right=$this->lowestCommonAncestor($root->right,$p,$q);//递归
if($left!
=null&&$right!
=null){//第一种情况
return$root;
}
if($left==null&&$right==null){//第二种情况
returnnull;
}
return$left==null?
$right:
$left;//第三种情况
}
}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- leetcode 力扣 236 二叉树的最近公共祖先 题解 算法题 二叉 最近 公共 祖先 算法