当前位置:网站首页>1123. The nearest common ancestor of the deepest leaf node
1123. The nearest common ancestor of the deepest leaf node
2022-07-07 01:20:00 【Mr Gao】
1123. The closest common ancestor of the deepest leaf node
Give you a root node root Two fork tree , Go back to it The nearest common ancestor of the deepest leaf node .
Think about it :
Leaf nodes Is a node in a binary tree that has no child nodes
Of the root node of the tree depth by 0, If the depth of a node is d, Then the depth of its child nodes is d+1
If we assume A It's a set of nodes S Of Recent public ancestor ,S Each node in the is represented by A In the subtree of the root node , And A The depth of reaches the maximum possible under this condition .
Example 1:
Input :root = [3,5,1,6,2,0,8,null,null,7,4]
Output :[2,7,4]
explain : Our return value is 2 The node of , Mark... In yellow in the figure .
What is marked in blue in the figure is the deepest node of the tree .
Be careful , node 6、0 and 8 It's also a leaf node , But their depth is 2 , And node 7 and 4 The depth of is 3 .
Example 2:
Input :root = [1]
Output :[1]
explain : The root node is the deepest node in the tree , It is its nearest common ancestor .
Example 3:
Input :root = [0,1,3,null,2]
Output :[2]
explain : The deepest leaf node in the tree is 2 , The recent public ancestor is itself .
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
#define size 100
int f(struct TreeNode* root){
if(root){
int a=f(root->left)+1;
int b=f(root->right)+1;
if(a>b){
return a;
}
return b;
}
else{
return 0;
}
}
struct TreeNode* lcaDeepestLeaves(struct TreeNode* root){
struct TreeNode *queue[size],*p;
struct TreeNode *re=NULL;
int front,rear;
int h=f(root);
front=0;
rear=0;
queue[rear]=root;
rear=(rear+1)%size;
queue[rear]=NULL;
rear=(rear+1)%size;
printf("h %d ",h);
int hz=1;
if(h==1){
re=root;
}
while(front!=rear){
p=queue[front];
front=(front+1)%size;
if(p==NULL&&front!=rear){
hz++;
queue[rear]=NULL;
rear=(rear+1)%size;
printf("hz %d ",hz);
}
else{
if(rear==front){
break;
}
printf("%d |",p->val);
if(hz==h-1){
if(p->left&&p->right){
re=p;
}
if(p->right&&p->left==NULL){
re=p->right;
}
if(p->left&&p->right==NULL){
re=p->left;
}
}
if(p->left){
queue[rear]=p->left;
rear=(rear+1)%size;
}
if(p->right){
queue[rear]=p->right;
rear=(rear+1)%size;
}
}
}
return re;
}
The following method should be better
1. Determine the depth of children around the current node , Equal, then the current node is the nearest common ancestor ;
2. If the depth of the left child is greater than that of the right child, the public ancestor must be on the left subtree ;
3. If the depth of the left child is less than that of the right child, the public ancestor must be on the right subtree ;
Traverse the tree and find a node with the same depth of the left and right subtrees .
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
int getDepth(struct TreeNode* root){
if(!root)return 0;
return fmax(getDepth(root->left),getDepth(root->right))+1;
}
struct TreeNode* lcaDeepestLeaves(struct TreeNode* root){
struct TreeNode* res=root,*cur=root;
while(cur){
int left=getDepth(cur->left);
int right=getDepth(cur->right);
if(left==right){
res=cur;
break;
}else if(left>right){
cur=cur->left;
}else cur=cur->right;
}
return res;
}
边栏推荐
- [Niuke] [noip2015] jumping stone
- 实现mysql与ES的增量数据同步
- 第三方跳转网站 出现 405 Method Not Allowed
- The MySQL database in Alibaba cloud was attacked, and finally the data was found
- 动态规划思想《从入门到放弃》
- NEON优化:关于交叉存取与反向交叉存取
- Supersocket 1.6 creates a simple socket server with message length in the header
- Maidong Internet won the bid of Beijing life insurance to boost customers' brand value
- Rainstorm effect in levels - ue5
- Wood extraction in Halcon
猜你喜欢
Come on, don't spread it out. Fashion cloud secretly takes you to collect "cloud" wool, and then secretly builds a personal website to be the king of scrolls, hehe
LLDP兼容CDP功能配置
Your cache folder contains root-owned files, due to a bug in npm ERR! previous versions of npm which
Do you understand this patch of the interface control devaxpress WinForms skin editor?
BFS realizes breadth first traversal of adjacency matrix (with examples)
golang中的Mutex原理解析
Send template message via wechat official account
云呐|工单管理软件,工单管理软件APP
Anfulai embedded weekly report no. 272: 2022.06.27--2022.07.03
黑马笔记---异常处理
随机推荐
2022 Google CTF SEGFAULT LABYRINTH wp
How to evaluate load balancing performance parameters?
ARM裸板调试之JTAG调试体验
2022 Google CTF segfault Labyrinth WP
接收用户输入,身高BMI体重指数检测小业务入门案例
【C语言进阶篇】指针的8道笔试题
Body mass index program, entry to write dead applet project
ARM裸板调试之JTAG原理
Taro2.* 小程序配置分享微信朋友圈
Oracle:CDB限制PDB资源实战
JTAG principle of arm bare board debugging
"Exquisite store manager" youth entrepreneurship incubation camp - the first phase of Shunde market has been successfully completed!
SuperSocket 1.6 创建一个简易的报文长度在头部的Socket服务器
实现mysql与ES的增量数据同步
Taro applet enables wxml code compression
Neon Optimization: About Cross access and reverse cross access
Data type of pytorch tensor
AI 从代码中自动生成注释文档
Wood extraction in Halcon
What are the differences between Oracle Linux and CentOS?