巧【二叉搜索树的最近公共祖先】【二叉搜索树的性质】Leetcode 235. 二叉搜索树的最近公共祖先

【二叉搜索树的最近公共祖先】【二叉搜索树性质】Leetcode 235. 二叉搜索树的最近公共祖先

    • 【巧】解法1 利用二叉搜索树有序的性质
    • 解法2 采用二叉树求最近公共祖先的方法——后序遍历

在这里插入图片描述

---------------🎈🎈235. 二叉搜索树的最近公共祖先 题目链接🎈🎈-------------------

【巧】解法1 利用二叉搜索树有序的性质

二叉搜索树的特点被应用
如果root大于p和q,说明p和q的最近公共祖先一定在当前节点的左子树中, 那么就只需要向左遍历
如果root小于p和q ,说明p和q的最近公共祖先一定在当前节点的右子树中, 那么就只需要向右遍历
如果root的值介于p和q之间,说明root一定是p和q的公共祖先,这时候返回root即可
—————————但需要怎么保证其是最近的公共祖先呢?其实二叉搜索树就直接保证了其是最近的

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if(root.val > p.val && root.val > q.val){  // 如果root大于p和q  那么就只需要向左遍历 结果不断return上去
            return lowestCommonAncestor(root.left,p,q);
        }
        if(root.val < p.val && root.val < q.val){ // 如果root小于p和q  那么就只需要向右遍历 结果不断return上去
            return lowestCommonAncestor(root.right,p,q);
        }
        // 如果等于或者root的值介于p和q之间,这时候返回root即可
        return root;

    }
}          
    

解法2 采用二叉树求最近公共祖先的方法——后序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root ==null) return null;
        if(root==p ||root==q) return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);

        if(left == null && right==null) return null;
        else if(left == null && right!=null) return right;
        else if(left != null && right==null) return left;
        else return root;
    }
}


本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/427714.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

帮公司面试了个要25K的测试,我问了他这些问题...

深耕IT行业多年&#xff0c;我们发现&#xff0c;对于一个程序员而言&#xff0c;能去到一线互联网公司&#xff0c;会给我们以后的发展带来多大的影响。 很多人想说&#xff0c;这个我也知道&#xff0c;但是进大厂实在是太难了&#xff0c;简历投出去基本石沉大海&#xff0…

YOLOV9训练集制作+Train+Val记录

一、YOLO数据集格式分布 在YOLO中&#xff0c;数据集的分布如图&#xff0c;在dataset文件夹下有imags&#xff08;图片&#xff09;和labels&#xff08;标签&#xff09;。在images和labels文件夹下又分别存放三个文件夹&#xff0c;分别对应测试集、训练集、验证集&#xff…

如何使用Python Flask发布web页面至公网并实现远程访问【内网穿透】

文章目录 1. 安装部署Flask2. 安装Cpolar内网穿透3. 配置Flask的web界面公网访问地址4. 公网远程访问Flask的web界面 本篇文章主要讲解如何在本地安装Flask&#xff0c;以及如何将其web界面发布到公网进行远程访问。 Flask是目前十分流行的web框架&#xff0c;采用Python编程语…

Java中的排序算法

引言&#xff1a; 当谈到编程语言中的排序&#xff0c;Java 作为一种广泛使用的编程语言&#xff0c;提供了许多强大的排序算法来满足不同的需求。排序是一种将一组数据按照特定顺序重新排列的过程&#xff0c;通常是按照升序或降序排列。在 Java 中&#xff0c;我们可以利用内…

【airtest】自动化入门教程(二)airtest操作

目录 一、touch 二、wait 三、swipe 四、exists 五、text 六、keyevent 七、snapshot 八、sleep 九、断言 9.1 assert_exists 9.2 assert_not_exists 9.3 assert_equal 9.4 assert_not_equal 前言&#xff1a;本文主要针对aritest部分的基础操作,aritest是一个跨平…

AJAX 学习笔记(Day3)

「写在前面」 本文为黑马程序员 AJAX 教程的学习笔记。本着自己学习、分享他人的态度&#xff0c;分享学习笔记&#xff0c;希望能对大家有所帮助。推荐先按顺序阅读往期内容&#xff1a; 1. AJAX 学习笔记&#xff08;Day1&#xff09; 目录 3 AJAX 原理 3.1 XMLHttpRequest 3…

遭遇CC攻击如何做防护策略

CC&#xff08;Challenge Collapsar&#xff09;攻击是一种常见而具有破坏力的拒绝服务攻击&#xff08;DDoS&#xff09;&#xff0c;对网络安全造成威胁。为了保护网络免受这类恶意攻击&#xff0c;采取有效的防护策略至关重要。本文将介绍一些可以帮助保护您的网络免受CC攻击…

appium环境搭建

一.appium环境搭建 1.python3 python3的下载安装这里就不多做介绍了&#xff0c;当然你也可以选择自己喜欢的语音&#xff0c;比如java… 2.jdk 1&#xff09;下载地址 官网(需登录账号)&#xff1a; https://www.oracle.com/java/technologies/downloads/ 百度网盘&…

windows server 2019 安装NET Framework 3.5失败,提示:“安装一个或多个角色、角色服务或功能失败” 解决方案

错误描述&#xff1a; windows server 2019 安装NET Framework 3.5失败&#xff0c;提示&#xff1a;“安装一个或多个角色、角色服务或功能失败”&#xff1a;“安装一个或多个角色、角色服务或功能失败错误: 0x800f0950” 。 错误原因&#xff1a; windows 2019 server系统…

【C语言】指针详细解读2

1.const 修饰指针 1.1 const修饰变量 变量是可以修改的&#xff0c;如果把变量的地址交给⼀个指针变量&#xff0c;通过指针变量的也可以修改这个变量。 但是如果我们希望⼀个变量加上⼀些限制&#xff0c;不能被修改&#xff0c;怎么做呢&#xff1f;这就是const的作⽤。 …

力扣hot100:1.两数之和

输入中可能存在重复值 。 分析&#xff1a; 本题需要返回的是数组下标&#xff0c;因此如果需要使用排序然后双指针的话&#xff0c;需要用到哈希表&#xff0c;但是由于输入中可能存在重复值&#xff0c;因此哈希表的value值必须是vector<int>。 使用双指针求目标值targ…

Deep Learning相关概念介绍

工具&#xff1a; Anaconda: anaconda.com/products/individual。我理解是一个基于Python的AI程序开发环境&#xff0c;其作用类似于google notebook。区别是google notebook是在网页上&#xff0c;而Anaconda一般是安装在自己的服务器上。Jupyter Notebooks Anaconda激活深度…

vscode使用git

更改的文件 点击号 &#xff0c; 相当于git add 添加到暂存区 -号 取消暂存区内容 可以查看更改的前后对比 编辑器左下角点击分支&#xff0c;可以创建新分支 提交到暂存区后&#xff0c;点击 提交 &#xff0c; 编辑备注内容 &#xff0c;相当于git commit -m 提交备注内容 同…

Leaflet 初始化地图

前言 &#x1f914;&#x1f914; Leaflet系列搁置了好久&#xff0c;趁着deadline来临之际&#xff0c;我会在两周内将这个专栏的内容基本更新完毕&#xff0c;并随着项目的精进将更多优质的文章内容提供给本专栏的订阅者&#xff1b;说正事&#xff0c;在本文中&#xff0c;我…

《精益DevOps》:填补IT服务交付的认知差距,实现高效可靠的客户期望满足

写在前面 在当今的商业环境中&#xff0c;IT服务交付已经成为企业成功的关键因素之一。然而&#xff0c;实现高效、可靠、安全且符合客户期望的IT服务交付却是一项艰巨的任务。这要求服务提供商不仅具备先进的技术能力&#xff0c;还需要拥有出色的组织协作、流程管理和态势感…

IMAP和SMTP的区别与联系是什么?如何区分?

IMAP和SMTP的区别有哪些&#xff1f;IMAP和SMTP选择哪个更好&#xff1f; 在电子邮件通信的过程中&#xff0c;两个关键协议扮演着不可或缺的角色&#xff0c;它们就是IMAP和SMTP。这两个协议各有特色&#xff0c;但又紧密相连&#xff0c;共同维护着电子邮件系统的稳定运行。…

Neo4j从入门到放弃

前言 本文记录前公司在开发社交应用时&#xff0c;探索Neo4j数据库记录的一些关键信息和常见问题。希望这篇文章的一些信息能对你有所帮助。少走一些弯路。Neo4j的学习最好在搭建完后&#xff0c;它的web管理界面有一个引导教程&#xff0c;跟着它的指导手册走下教程&#xff…

内网穿透的应用-如何修改Nginx服务location代理转发规则结合cpolar实现无公网ip环境访问内网站点

文章目录 1. 下载windows版Nginx2. 配置Nginx3. 测试局域网访问4. cpolar内网穿透5. 测试公网访问6. 配置固定二级子域名7. 测试访问公网固定二级子域名 1. 下载windows版Nginx 进入官方网站(http://nginx.org/en/download.html)下载windows版的nginx 下载好后解压进入nginx目…

【FastChat】用于训练、服务和评估大型语言模型的开放平台

FastChat 用于训练、服务和评估大型语言模型的开放平台。发布 Vicuna 和 Chatbot Arena 的存储库。 隆重推出 Vicuna&#xff0c;一款令人印象深刻的开源聊天机器人 GPT-4&#xff01; &#x1f680; 根据 GPT-4 的评估&#xff0c;Vicuna 达到了 ChatGPT/Bard 90%* 的质量&…

HQL,SQL刷题,尚硅谷

目录 相关表数据&#xff1a; ​编辑 题目及思路解析&#xff1a; 复杂查询&#xff0c;子查询 1、查询所有课程成绩均小于60分的学生的学号、姓名 2、查询没有学全所有课的学生的学号、姓名 3、查询出只选修了三门课程的全部学生的学号和姓名 总结归纳&#xff1a; 知识补充&a…