当前位置:网站首页>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;
}
};
边栏推荐
- Vscode configuration uses pylint syntax checker
- Clickhouse (03) how to install and deploy Clickhouse
- Redis 核心数据结构 & Redis 6 新特性详
- 数据流图,数据字典
- [Reading stereo matching papers] [III] ints
- FCOS3D label assignment
- Is it safe to open an account online now? Which securities company should I choose to open an account online?
- Assign a dynamic value to the background color of DataGrid through ivalueconverter
- 多商户商城系统功能拆解01讲-产品架构
- Mysql怎样控制replace替换的次数?
猜你喜欢
一个简单LEGv8处理器的Verilog实现【四】【单周期实现基础知识及模块设计讲解】
Horizontal of libsgm_ path_ Interpretation of aggregation program
Best practice | using Tencent cloud AI willingness to audit as the escort of telephone compliance
Battle Atlas: 12 scenarios detailing the requirements for container safety construction
Transferring files between VMware and host
Flask session forged hctf admin
Selenium库
MRS离线数据分析:通过Flink作业处理OBS数据
Introduction to sakt method
Data flow diagram, data dictionary
随机推荐
c#通过frame 和 page 切换页面
多商户商城系统功能拆解01讲-产品架构
交换机和路由器的异同
请问,PTS对数据库压测有好方案么?
Excuse me, as shown in the figure, the python cloud function prompt uses the pymysql module. What's the matter?
【立体匹配论文阅读】【三】INTS
Seven propagation behaviors of transactions
MySQL "invalid use of null value" solution
[high frequency interview questions] difficulty 2.5/5, simple combination of DFS trie template level application questions
How can the PC page call QQ for online chat?
Supply chain supply and demand estimation - [time series]
现在网上开户安全么?那么网上开户选哪个证券公司?
NDK beginner's study (1)
Excellent open source system recommendation of ThinkPHP framework
ES日志报错赏析-Limit of total fields
最长上升子序列模型 AcWing 1012. 友好城市
C # use TCP protocol to establish connection
用例图
参数关键字Final,Flags,Internal,映射关键字Internal
PHP中用下划线开头的变量含义