当前位置:网站首页>Leetcode -- the nearest common ancestor of 236 binary tree
Leetcode -- the nearest common ancestor of 236 binary tree
2022-07-02 10:13:00 【_ End, broken string】
The nearest common ancestor of a binary tree
Train of thought
subject
If the interviewer asks the nearest common ancestor of a binary tree , We can ask the interviewer , Is this binary tree a search tree , If it's a search tree
Here's the picture :
The characteristic of search tree is : The left child is younger than his father , The right child is older than his father . Then we can analyze :2,3 The most recent public ancestor of 3,0,4 The most recent public ancestor of 3, 6 and 9 My nearest ancestor was 7. Then it can be concluded that : A child node is smaller than the root , A child node is larger than the root , This root is the nearest common ancestor , If 2 There are... In nodes 1 The first is the root node, so this node is the nearest common ancestor
Ordinary binary tree
From the above ideas :
1.2 All nodes are in the left subtree , Recurse to the left tree to find
2.2 All nodes are in the right subtree , Recurse to the right tree to find
3. If 1 One on the left and one on the right , The root node is the nearest common ancestor , If 2 There are... In nodes 1 The first is the root node, so this node is the nearest common ancestor
At this time, you need to write a recursive search node , here Node to be used
To compare , Out-of-service val
To compare , If val There will be miscarriage of justice . Also pay attention to naming , Bad naming is easy to confuse others , Or the interviewer doesn't give a score .
The code is as follows :
class Solution {
public:
bool find(TreeNode* root,TreeNode* x)
{
//root Empty to return directly to
if(root == nullptr)
return false;
if(root == x)
return true;
// If you are not in the left subtree, go to the right subtree , Use or here
return find(root->left,x) || find(root->right,x);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// If 2 Among them 1 The first is the root. At this time, the root is the nearest public ancestor
if(p == root || q == root)
{
return root;
}
// Definition 4 individual bool value , Namely p In the left subtree and the right subtree
//q and p Just the same
bool pInLeft,pInRght,qInLeft,qInRght;
//p On the left, it won't be in the right subtree
//q It's the same operation
pInLeft = find(root->left,p);
pInRght = !pInLeft;
qInLeft = find(root->left,q);
qInRght = !qInLeft;
// If 2 All of them are in the left subtree , Continue to recurse to the left subtree to find
if(pInLeft && qInLeft)
{
return lowestCommonAncestor(root->left,p,q);
}
// If 2 All of them are in the right subtree , Continue to recurse to the right subtree to find
else if(pInRght && qInRght)
{
return lowestCommonAncestor(root->right,p,q);
}
// One on the left and one on the right , The root is the nearest common ancestor
else
{
return root;
}
}
};
analysis : If the binary tree is a full binary tree or a complete binary tree , The time complexity at this time is O(nlogn), The extreme case is a single tree , The time complexity at this time is O(N^2). At this time, the time complexity required by the interviewer is O(N), Then how to solve it ?
Train of thought two
look for 2 The path of nodes , Use the stack to save the path , To find the intersection node .
The code is as follows :
class Solution {
public:
bool findPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
{
if(root == nullptr)
return false;
// If the root node is not empty, enter the stack
path.push(root);
if(root == x)
return true;
// Found return true
if (findPath(root->left,x,path))
{
return true;
}
if(findPath(root->right,x,path))
{
return true;
}
// It's not the right path to go here ,pop take false Back to the next level
path.pop();
return false;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// Definition 2 Stack save path
stack<TreeNode*> pPath;
stack<TreeNode*> qPath;
// find p and q The path of
findPath(root,p,pPath);
findPath(root,q,qPath);
// use 2 Pointer to compare the length
stack<TreeNode*>*shortPath = &pPath;
stack<TreeNode*>*longtPath = &qPath;
// I don't know which path is long , At this time, it defaults to 1 Long , In comparison , If the default long and short are exchanged
if(pPath.size() > qPath.size())
{
swap(shortPath,longtPath);
}
// Let the long walk the gap first , Walking at the same time
while(shortPath->size() < longtPath->size())
{
longtPath->pop();
}
// Walk at the same time and compare whether the elements at the top of the stack are equal , The first 1 Even the nearest common ancestor
while(shortPath->top() != longtPath->top())
{
longtPath->pop();
shortPath->pop();
}
return shortPath->top();
}
};
We just passed .
analysis :
It can be seen that thinking two is much faster than one , Time complexity analysis :2 The path to stack is O(N),2 Stack comparison is also O(N), That is to say O(4N), The final time complexity is O(N).
边栏推荐
- Remember the use of add method once
- Following nym, the new project Galaxy token announced by coinlist is gal
- ESLint 报错
- 【虚幻】过场动画笔记
- Introduction et prévention des essais de pénétration
- go语言入门
- Large neural networks may be beginning to realize: the chief scientist of openai leads to controversy, and everyone quarrels
- Ue5 - AI pursuit (blueprint, behavior tree)
- UE4夜间打光笔记
- 2837xd 代码生成——补充(2)
猜你喜欢
【UE5】动画重定向:如何将幻塔人物导入进游戏玩耍
Introduction et prévention des essais de pénétration
Attack and defense world web advanced area unserialize3
Tee command usage example
【虚幻】按键开门蓝图笔记
Alibaba cloud Prometheus monitoring service
阿里云SLS日志服务
High level application of SQL statements in MySQL database (II)
AutoCAD - layer Linetype
Bugkuctf-web24 (problem solving ideas and steps)
随机推荐
The latest progress and development trend of 2022 intelligent voice technology
Minimum number of C language
[200 Shengxin literatures] 96 joint biomarkers of immune checkpoint inhibitor response in advanced solid tumors
Idempotent design of Internet API interface
ue4材质的入门和原理笔记
Centos7 one click compilation and installation of PHP script
Junit5 支持suite的方法
UE4 night lighting notes
XA Transaction SQL Statements
Record personal understanding and experience of game console configuration
2837xd 代码生成——StateFlow(4)
滲透測試的介紹和防範
【虚幻】自动门蓝图笔记
Off grid control of three-phase inverter - PR control
Configuration programmée du générateur de plantes du moteur illusoire UE - - Comment générer rapidement une grande forêt
职业规划和发展
2837xd代码生成模块学习(1)——GPIO模块
C language strawberry
Bugkuctf-web16 (backup is a good habit)
ZK configuration center -- configuration and use of config Toolkit