当前位置:网站首页>【LeetCode 43】236. The nearest common ancestor of binary tree
【LeetCode 43】236. The nearest common ancestor of binary tree
2022-07-02 01:34:00 【CodeLinghu】
【LeetCode 43】236. The nearest common ancestor of a binary tree
List of articles
One 、 The question
Two 、 The answer process
** Ideas / Method :** This question uses bottom-up search ------ to flash back
! Recursion is also used !
If you find a node , It is found that there are nodes in the left subtree p, A node appears in the right subtree q, perhaps Nodes appear in the left subtree q, A node appears in the right subtree p, So the node is the node p and q The latest public ancestor of .
Use After the sequence traversal , Backtracking process , It is to traverse nodes from low to high , Once the node of this condition is found , It's the nearest public node .
- First find the node path p and q
- At the nearest common ancestor node of the node path
Logical processing in recursive trilogy :
//
//3. Traverse the whole tree
TreeNode *left=lowestCommonAncestor(root->left,p,q);
TreeNode *right=lowestCommonAncestor(root->right,p,q);
When a recursive function has a return value :
- Search for an edge :
if ( Recursive function (root->left)) return ;
if ( Recursive function (root->right)) return ;
- Search the whole tree :
left = Recursive function (root->left);
right = Recursive function (root->right);
left And right Logical processing of ;
When a recursive function has a return value : If you want to search for an edge , When the return value of recursive function is not empty , Go back to , If you search the whole tree , Just use a variable left、right Catch the return value , This left、right There is also the need for logic processing in the post order , That is to say, the logic to deal with intermediate nodes in post order traversal ( It's also retrospective )
class Solution {
public://1.
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//2. If a node is found p Or nodes q Or an empty node is encountered . Just go back to
if(root==q||root==p||root==NULL) return root;
//3. Traverse the whole tree
TreeNode *left=lowestCommonAncestor(root->left,p,q);// Constantly traverse the left subtree
TreeNode *right=lowestCommonAncestor(root->right,p,q);// Constantly traverse the right subtree
// Discussion :
if(left!=NULL&&right!=NULL) return root;
if(left==NULL&&right!=NULL) return right;
else if(left!=NULL&&right==NULL) return left;
else{
//left==NULL&&right==NULL
return NULL;
}
}
};
边栏推荐
- Based on Simulink and FlightGear, the dynamic control of multi rotor UAV in equilibrium is modeled and simulated
- Introduction to ffmpeg Lib
- Learn about servlets
- Quatre stratégies de base pour migrer la charge de travail de l'informatique en nuage
- A problem about function template specialization
- 关于ASP.NET CORE使用DateTime日期类型参数的一个小细节
- [IVX junior engineer training course 10 papers] 05 canvas and aircraft war game production
- Matlab uses audioread and sound to read and play WAV files
- MATLAB realizes voice signal resampling and normalization, and plays the comparison effect
- Basic usage of shell script
猜你喜欢
Quatre stratégies de base pour migrer la charge de travail de l'informatique en nuage
Since I understand the idea of dynamic planning, I have opened the door to a new world
GL Studio 5 installation and experience
Matlab uses audioread and sound to read and play WAV files
Hcip day 14 (MPLS protocol)
matlab 使用 resample 完成重采样
I'll teach you to visit Amazon RDS for a year and build a MySQL cloud database (only 10 minutes, really fragrant)
Learning notes 25 - multi sensor front fusion technology
机器学习基本概念
[rust web rokcet Series 2] connect the database and add, delete, modify and check curd
随机推荐
CTF daily question day45 sensor
The role of artificial intelligence in network security
技术大佬准备就绪,话题C位由你决定
ECS project deployment
MySQL winter vacation self-study 2022 12 (4)
[rust web rokcet Series 1] Hello, world and get, post, put, delete
卷积神经网络(包含代码与相应图解)
Altium designer measure distance (ctrl+m)
SAP ui5 beginner tutorial XXI - trial version of custom formatter of SAP ui5
The technology boss is ready, and the topic of position C is up to you
Daily work and study notes
The concept and application of Cartland number
Part 29 supplement (XXIX) basis of ECMAScript
[disease detection] realize lung cancer detection system based on BP neural network, including GUI interface
Laravel artisan 常用命令
迁移云计算工作负载的四个基本策略
No converter found for return value of type: class
Six lessons to be learned for the successful implementation of edge coding
遊戲思考15:全區全服和分區分服的思考
This is the form of the K-line diagram (pithy formula)