当前位置:网站首页>Leetcode——236. 二叉树的最近公共祖先
Leetcode——236. 二叉树的最近公共祖先
2022-07-07 12:15:00 【styfish】
概述
分析
题目要求找树中等两个节点的最近公共祖先,容易想到应该从下往上查找,进而想到使用后序遍历
通过后序遍历,可以从树的下面开始遍历一个结点的左右子树,如果左右子树分别有指定的结点的话,则该节点一定是最低的公共祖先
因为后序一定是从下面开始的,如果左右子树中有指定结点的话,那么一定是第一次出现
思路
如何确定左右子树是否拥有指定的结点?
- 遍历过程中,判断遍历的节点是否和指定结点相同,如果相同,则返回该结点
代码
class Solution {
public:
// 4. 确定递归函数返回值
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// 1. 确定递归函数
// 3. 确定终止条件。 如果节点==p、q则说明找到了;如果节点=nullptr,则遍历结束
if (root == p || root == q || root = nullptr) {
// 如果找到指定的节点 or 为空节点
return root;
}
// 1. 确定单层递归逻辑————后序遍历
TreeNode *lNode=lowestCommonAncestor(root -> left, p, q);
TreeNode *rNode=lowestCommonAncestor(root -> right, p, q);
// 2. 明确递归函数的作用
// lowestCommonAncestor的作用:判断在以root节点为根的子树中,是否拥有p、q指向的结点
if (lNode != nullptr && rNode != nullptr) // 如果在左右子树中,
return root;
else if(lNode == nullptr) {
//两个都在右子树
return rNode;
}
else {
//两个都在左子树里面
return lNode;
}
return nullptr;
}
};
边栏推荐
- Regular expression integer positive integer some basic expressions
- 请问指南针股票软件可靠吗?交易股票安全吗?
- Laravel5 call to undefined function OpenSSL cipher IV length() error php7 failed to open OpenSSL extension
- [high frequency interview questions] difficulty 2.5/5, simple combination of DFS trie template level application questions
- 【网络安全】sql注入语法汇总
- Introduction to sakt method
- 股票开户首选,炒股交易开户佣金最低网上开户安全吗
- Realization of search box effect [daily question]
- 杭电oj2054 A == B ? ???
- ES日志报错赏析-Limit of total fields
猜你喜欢
Social responsibility · value co creation, Zhongguancun network security and Information Industry Alliance dialogue, wechat entrepreneur Haitai Fangyuan, chairman Mr. Jiang Haizhou
Codes de non - retour à zéro inversés, codes Manchester et codes Manchester différentiels couramment utilisés pour le codage des signaux numériques
Parsing of XML files
PERT图(工程网络图)
566. Reshaping the matrix
使用day.js让时间 (显示为几分钟前 几小时前 几天前 几个月前 )
Hands on Teaching: XML modeling
Assign a dynamic value to the background color of DataGrid through ivalueconverter
一个简单LEGv8处理器的Verilog实现【四】【单周期实现基础知识及模块设计讲解】
Battle Atlas: 12 scenarios detailing the requirements for container safety construction
随机推荐
Details of redis core data structure & new features of redis 6
c#通过frame 和 page 切换页面
Csma/cd carrier monitoring multipoint access / collision detection protocol
AI talent cultivation new ideas, this live broadcast has what you care about
call undefined function openssl_ cipher_ iv_ length
Huawei image address
GVIM [III] [u vimrc configuration]
Laravel form builder uses
接口自动化测试-接口间数据依赖问题解决
Seven propagation behaviors of transactions
PERT图(工程网络图)
2022-7-6 Leetcode27. Remove the element - I haven't done the problem for a long time. It's such an embarrassing day for double pointers
IP and long integer interchange
. Net core about redis pipeline and transactions
股票开户首选,炒股交易开户佣金最低网上开户安全吗
Flask session forged hctf admin
手里的闲钱是炒股票还是买理财产品好?
libSGM的horizontal_path_aggregation程序解读
PostgreSQL array type, each splice
课设之百万数据文档存取