当前位置:网站首页>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).
边栏推荐
- 阿里云SLS日志服务
- 2837xd code generation - Supplement (1)
- Project practice, redis cluster technology learning (IX)
- 虚幻AI蓝图基础笔记(万字整理)
- PI control of three-phase grid connected inverter - off grid mode
- Bookmark collection management software suspension reading and data migration between knowledge base and browser bookmarks
- Bugkuctf-web16 (backup is a good habit)
- Translation d30 (with AC code POJ 28:sum number)
- Introduction et prévention des essais de pénétration
- Commutateur Multi - lentilles Blender
猜你喜欢
Skywalking theory and Practice
ZK configuration center -- configuration and use of config Toolkit
Ue5 - AI pursuit (blueprint, behavior tree)
阿里云SLS日志服务
This monitoring system makes workers tremble: turnover intention and fishing can be monitored. After the dispute, the product page has 404
Skywalking理论与实践
Tools used for Yolo object recognition and data generation
Memories of a chat
UE illusory engine programmed plant generator setup -- how to quickly generate large forests
ESLint 报错
随机推荐
ue虚幻引擎程序化植物生成器设置——如何快速生成大片森林
阿里云Prometheus监控服务
Tools used for Yolo object recognition and data generation
Commutateur Multi - lentilles Blender
Tee command usage example
Alibaba cloud SMS service
2837xd code generation - Summary
Project practice, redis cluster technology learning (13)
Remember a simple Oracle offline data migration to tidb process
Bugkuctf-web21 (detailed problem solving ideas and steps)
The latest progress and development trend of 2022 intelligent voice technology
Summary of demand R & D process nodes and key outputs
C language: making barrels
Judging right triangle in C language
【UE5】AI随机漫游蓝图两种实现方法(角色蓝图、行为树)
PI control of three-phase grid connected inverter - off grid mode
How does {} prevent SQL injection? What is its underlying principle?
What wires are suitable for wiring on bread board?
2837xd 代码生成——StateFlow(4)
Image recognition - Data Acquisition