当前位置: 首页 > news >正文

二叉树的最近公共祖先

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻强烈推荐优质专栏: 🍔🍟🌯C++的世界(持续更新中)
🐻推荐专栏1: 🍔🍟🌯C语言初阶
🐻推荐专栏2: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一
🍉本篇简介:>:记录力扣题 二叉树的最近公共祖先.
金句分享:
✨生活本就沉默,但是跑起来有风!✨

前言

目录

  • 前言
    • 题目介绍:
    • 解题思路
    • 代码实现:

题目来源于:力扣
题目链接:传送门

题目介绍:

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
在这里插入图片描述

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3

解释:节点 5 和节点 1 的最近公共祖先是节点 3 。

在这里插入图片描述

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出:5

解释:节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

解题思路

幻想:
如果该树是三叉树就好了,有一个指向父亲的指针,那样就可以转化为两个链表相交,求交点,只需要快慢指针就行了.

正经解题:

  1. 试着观察最近公共祖先,如果只是普通的祖先,则这两个结点都在其中的一个子树中.
    (1)全在该结点的左子树 (2)全在该结点的右子树
  2. 如果是最近的公共祖先,则一个结点在左子树,一个在右子树.
  3. (1) 如果全在左子树,则往左子树方向继续找.
    (2) 如果全在右子树,同理;
  4. 特殊情况,其中一个是另一个的祖先(父亲),直接返回该结点(祖先)即可.

在这里插入图片描述

代码实现:

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root==p||root==q)	//其中一个是另一个的祖先{return root;}//判断在不在左子树bool left_p=find(root->left,p);bool left_q=find(root->left,q);//判断在不在右子树bool right_p=!left_p;bool right_q=!left_q;if(left_p && left_q){//如果全在左子树,则往左子树继续遍历root=lowestCommonAncestor( root->left,p,q);}else if(right_p && right_q){//如果全在右子树,则往右子树继续遍历root=lowestCommonAncestor( root->right,p,q);}return root;}bool find(TreeNode* root,TreeNode* node){if(root==nullptr) return false;if(root==node){return true;}return find(root->left,node)||find(root->right,node);}
};
http://www.lryc.cn/news/189280.html

相关文章:

  • C++ 补充 反向迭代器的实现
  • JVM第一讲:JVM相关知识体系详解+面试(P6熟练 P7精通)
  • 深度学习DAY3:FFNNLM前馈神经网络语言模型
  • JavaSE学习值之--String类
  • 【LeetCode高频SQL50题-基础版】打卡第6天:第31~35题
  • 基于单片机的汽车智能仪表的设计
  • 【Docker 内核详解】namespace 资源隔离(一):进行 namespace API 操作的 4 种方式
  • 【技术研究】环境可控型原子力显微镜超高真空度精密控制解决方案
  • 【Vuex+ElementUI】Vuex中取值存值以及异步加载的使用
  • python经典百题之简单加密数据
  • 登陆认证权限控制(1)——从session到token认证的变迁 session的问题分析 + CSRF攻击的认识
  • 单点接地、多点接地、混合接地
  • 【C++初阶(一)】学习前言 命名空间与IO流
  • flask vue跨域问题
  • stm32(二十)IAP升级优化(双缓存,可恢复)
  • HDLbits:Exams/ece241 2013 q4
  • 什么是React的虚拟DOM(Virtual DOM)?它的作用是什么?
  • Response Status Code 301、302
  • import { ref, onMounted, reactive } from ‘vue‘
  • 【TB作品】基于MSP430G2553单片机的超声波测距与报警系统,原理图,PCB
  • npm install报错
  • Flutter自定义model实体类
  • java项目实现不停服更新的4种方案(InsCode AI 创作助手)
  • 7.1 yolov5优化模型时,自动标注xml数据
  • 开发者职场“生存状态”大调研报告分析 - 第一版
  • 在MySQL中使用!=还能走索引吗?
  • 【算法题】2897. 对数组执行操作使平方和最大
  • 2023年中国划船机产量、销量及市场规模分析[图]
  • Kafka和RabbitMQ的对比
  • ffmpeg从一个视频中提取音频