当前位置:网站首页>Leetcode——236. The nearest common ancestor of binary tree
Leetcode——236. The nearest common ancestor of binary tree
2022-07-07 14:18:00 【styfish】
summary
236. The nearest common ancestor of a binary tree
analysis
The problem requires finding the nearest common ancestor of two nodes in the tree , It's easy to think of finding it from the bottom up , Then I think of using post order traversal
Through post order traversal , You can traverse the left and right subtrees of a node from the bottom of the tree , If the left and right subtrees have specified nodes respectively , Then the node must be the lowest common ancestor
Because the sequence must start from the following , If there are specified nodes in the left and right subtrees , Then it must be the first time
Ideas
How to determine whether the left and right subtrees have specified nodes ?
- During traversal , Judge whether the traversal node is the same as the specified node , If the same , The node is returned
Code
class Solution {
public:
// 4. Determine the return value of recursive function
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// 1. Determine the recursive function
// 3. Determine termination conditions . If node ==p、q It says it found it ; If node =nullptr, Then the traversal ends
if (root == p || root == q || root = nullptr) {
// If the specified node is found or Is an empty node
return root;
}
// 1. Determine single level recursive logic ———— After the sequence traversal
TreeNode *lNode=lowestCommonAncestor(root -> left, p, q);
TreeNode *rNode=lowestCommonAncestor(root -> right, p, q);
// 2. Clarify the role of recursive functions
// lowestCommonAncestor The role of : Judgment is based on root In the subtree whose node is the root , Owned or not p、q Pointed node
if (lNode != nullptr && rNode != nullptr) // If in the left and right subtrees ,
return root;
else if(lNode == nullptr) {
// Both are in the right subtree
return rNode;
}
else {
// Both are in the left subtree
return lNode;
}
return nullptr;
}
};
边栏推荐
- oracle 非自动提交解决
- [fortress machine] what is the difference between cloud fortress machine and ordinary fortress machine?
- Excusez - moi, l'exécution a été réussie lors de l'utilisation des données de puits SQL Flink à Kafka, mais il n'y a pas de nombre dans Kafka
- UML 顺序图(时序图)
- 股票开户首选,炒股交易开户佣金最低网上开户安全吗
- GVIM [III] [u vimrc configuration]
- 【网络安全】sql注入语法汇总
- FCOS3D label assignment
- Lavarel之环境配置 .env
- Similarities and differences between switches and routers
猜你喜欢
AI talent cultivation new ideas, this live broadcast has what you care about
SAKT方法部分介绍
Hands on Teaching: XML modeling
最长上升子序列模型 AcWing 1012. 友好城市
Horizontal of libsgm_ path_ Interpretation of aggregation program
一个简单LEGv8处理器的Verilog实现【四】【单周期实现基础知识及模块设计讲解】
Take you to master the three-tier architecture (recommended Collection)
[fortress machine] what is the difference between cloud fortress machine and ordinary fortress machine?
2022-7-7 Leetcode 844. Compare strings with backspace
Vmware 与主机之间传输文件
随机推荐
Clickhouse (03) how to install and deploy Clickhouse
C # switch pages through frame and page
杭电oj2092 整数解
[high frequency interview questions] difficulty 2.5/5, simple combination of DFS trie template level application questions
股票开户首选,炒股交易开户佣金最低网上开户安全吗
Leetcode——344. 反转字符串/541. 反转字符串 II/151. 颠倒字符串中的单词/剑指 Offer 58 - II. 左旋转字符串
交换机和路由器的异同
参数关键字Final,Flags,Internal,映射关键字Internal
【立体匹配论文阅读】【三】INTS
Parsing of XML files
requires php ~7.1 -> your PHP version (7.0.18) does not satisfy that requirement
Hangdian oj2092 integer solution
Transferring files between VMware and host
Reverse non return to zero code, Manchester code and differential Manchester code of common digital signal coding
SSRF vulnerability file pseudo protocol [netding Cup 2018] fakebook1
Is it safe to open an account online now? Which securities company should I choose to open an account online?
通过 iValueConverter 给datagrid 的背景颜色 动态赋值
Horizontal of libsgm_ path_ Interpretation of aggregation program
mysql导入文件出现Data truncated for column ‘xxx’ at row 1的原因
Supply chain supply and demand estimation - [time series]