当前位置:网站首页>The nearest common ancestor of binary (search) tree ●●
The nearest common ancestor of binary (search) tree ●●
2022-07-06 22:13:00 【chenyfan_】
236. The nearest common ancestor of a binary tree ●●
describe
Given a binary tree , Find two specified nodes in the tree Recent public ancestor .
The most recent definition of public ancestor is :“ For a tree T Two nodes of p、q, The nearest common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible ( A node can also be its own ancestor ).”
Example
Input :root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output :5
explain : node 5 And nodes 4 The most recent public ancestor of is the node 5 . Because by definition, the nearest common ancestor node can be the node itself .
Answer key
1. After the sequence traversal ( to flash back )
The first thing you can easily think of : 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 .
But there is a second situation , Is the node itself p(q), It has a grandchild node q§.
Use post order traversal , The process of backtracking , Namely Traverse nodes from low to high , Once the node satisfying the first condition is found , This is the nearest public node .
But if p perhaps q Itself is the nearest public ancestor ?
Actually Just find a node that is p perhaps q When , Return the current node directly , There is no need to continue recursive subtrees . If the next ( Up ) The following node is found in the traversal ( Parent node ) If the first condition is met, the return value is modified to the subsequent node , otherwise , Continue to return to the found node .
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 ( Recursive function (root->left)) return ;
if ( Recursive function (root->right)) return ;
If you want to 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 ).
left = Recursive function (root->left);
right = Recursive function (root->right);
left And right Logical processing of ;
- Time complexity O(N) : among N Is the number of binary tree nodes ; In the worst case , You need to recursively traverse all the nodes of the tree .
- Spatial complexity O(N) : In the worst case , The depth of recursion reaches N , System use O(N) The size of the extra space .
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == q || root == p || root == NULL) return root; // Judge the current node
TreeNode* left = lowestCommonAncestor(root->left, p, q); // Traverse left subtree
TreeNode* right = lowestCommonAncestor(root->right, p, q); // Traversal right subtree
if(left != NULL && right != NULL){
return root; // Both left and right subtrees have return values , Then the current is the nearest common ancestor
}else if(left != NULL){
return left; // Only the left subtree has a return value
}else if(right != NULL){
return right; // Only the right subtree has a return value
}
return NULL;
}
};
235. The nearest common ancestor of a binary search tree ●
describe
Given a binary search tree , Find two specified nodes in the tree Recent public ancestor .
The most recent definition of public ancestor is :“ For a tree T Two nodes of p、q, The nearest common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible ( A node can also be its own ancestor ).”
Example
p = 4, q = 7; Output : 6
p = 2, q = 4; Output : 2
Answer key
Different from ordinary binary tree , Binary search trees are ordered , as long as Traverse from top to bottom When ,cur The node is the value in [p, q] In interval It indicates that the node cur It's the recent public ancestor , And you don't need to traverse the whole tree , Find the result and return directly .
1. Sequence traversal queue iteration
The search direction is not adjusted according to the size of the node , Low efficiency .
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
int Min = min(p->val, q->val);
int Max = max(p->val, q->val);
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
TreeNode* curr = que.front();
que.pop();
if(curr->val <= Max && curr->val >= Min) return curr;
if(curr->left) que.push(curr->left);
if(curr->right) que.push(curr->right);
}
return NULL;
}
};
2. The former sequence traversal
Judge and adjust the search direction according to the size of the node .
When the node value is greater than p、q When the value of , Search to the left subtree ;
When the node value is less than p、q When the value of , Search the right subtree ;
Otherwise, the node value is in the interval , Meet the conditions , Go straight back to .
recursive
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == NULL) return NULL;
if(root->val > p->val && root->val > q->val){
// in
TreeNode* left = lowestCommonAncestor(root->left, p, q); // Left
if(left != NULL) return left;
}
if(root->val < p->val && root->val < q->val){
TreeNode* right = lowestCommonAncestor(root->right, p, q); // Right
if(right != NULL) return right;
}
return root; // Node value is within the range
}
};
iteration
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while(root != NULL){
if(root->val > p->val && root->val > q->val){
root = root->left; // To the left
}else if(root->val < p->val && root->val < q->val){
root = root->right; // To the right
}else return root; // Node value is within the range
}
return NULL;
}
};
边栏推荐
- Management background --5, sub classification
- Kohana database
- Mongodb (III) - CRUD
- Huawei has launched attacks in many industries at the same time, and its frightening technology has made European and American enterprises tremble
- GPS from getting started to giving up (16), satellite clock error and satellite ephemeris error
- [Chongqing Guangdong education] Information Literacy of Sichuan Normal University: a new engine for efficiency improvement and lifelong learning reference materials
- HDU 2008 digital statistics
- Xiaoman network model & http1-http2 & browser cache
- bat脚本学习(一)
- 20 large visual screens that are highly praised by the boss, with source code templates!
猜你喜欢
HDR image reconstruction from a single exposure using deep CNNs阅读札记
The golden age of the U.S. technology industry has ended, and there have been constant lamentations about chip sales and 30000 layoffs
AI 企业多云存储架构实践 | 深势科技分享
Reset Mikrotik Routeros using netinstall
Earned value management EVM detailed explanation and application, example explanation
GNN, please deepen your network layer~
GPS从入门到放弃(十三)、接收机自主完好性监测(RAIM)
Management background --3, modify classification
Barcodex (ActiveX print control) v5.3.0.80 free version
ZABBIX proxy server and ZABBIX SNMP monitoring
随机推荐
20 large visual screens that are highly praised by the boss, with source code templates!
AI enterprise multi cloud storage architecture practice | Shenzhen potential technology sharing
414. The third largest digital buckle
小满网络模型&http1-http2 &浏览器缓存
Kohana 数据库
About the professional ethics of programmers, let's talk about it from the way of craftsmanship and neatness
[sciter bug] multi line hiding
GPS du début à l'abandon (XIII), surveillance autonome de l'intégrité du récepteur (raim)
ZABBIX proxy server and ZABBIX SNMP monitoring
Mongodb (III) - CRUD
GPS从入门到放弃(十二)、 多普勒定速
HDU 4912 paths on the tree (lca+)
GPS from getting started to giving up (19), precise ephemeris (SP3 format)
How does the uni admin basic framework close the creation of super administrator entries?
Unity3D学习笔记6——GPU实例化(1)
C#实现水晶报表绑定数据并实现打印4-条形码
[leetcode daily clock in] 1020 Number of enclaves
中国VOCs催化剂行业研究与投资战略报告(2022版)
Oracle control file and log file management
Write a rotation verification code annotation gadget with aardio