算法打卡day18|二叉树篇07|Leetcode 530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数、236. 二叉树的最近公共祖先

 算法题

Leetcode  530.二叉搜索树的最小绝对差

题目链接:530.二叉搜索树的最小绝对差

大佬视频讲解:二叉搜索树的最小绝对差视频讲解

个人思路

因为是在二叉搜索树求绝对差,而二叉搜索树是有序的,那就把它想成在一个有序数组上求最值,求差值。采用中序遍历的递归,遍历所有节点,求出最小值

解法
递归法

使用二叉搜索树的特性,利用中序遍历就能把二叉树按照递增 序列去遍历,如下图;

class Solution {
    TreeNode pre;// 记录上一个遍历的结点
    int result = Integer.MAX_VALUE;//存最小绝对值的结果

    public int getMinimumDifference(TreeNode root) {
       if(root==null)return 0;
       traversal(root);
       return result;
    }

    public void traversal(TreeNode root){
        if(root==null)return;//终止条件

        traversal(root.left); //左
       
        if(pre!=null){ //中
            result = Math.min(result,root.val-pre.val);//取差值绝对值最小
        }
        pre = root;
        
        traversal(root.right);//右
    }
}

时间复杂度:O(n);(遍历整棵树)

空间复杂度:O(n);(递归树的高度,如果是一个高度不平衡的树(例如链状结构)高度与n接近)

迭代法

中序遍历的迭代法模板,再加上前一个节点pre,遍历取最小绝对值;

class Solution {
    TreeNode pre;
    Stack<TreeNode> stack;
    public int getMinimumDifference(TreeNode root) {
        if (root == null) return 0;
        stack = new Stack<>();//模拟递归的栈

        TreeNode cur = root;//当前节点
        int result = Integer.MAX_VALUE;

        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur); // 将访问的节点放进栈
                cur = cur.left; // 左

            }else {
                cur = stack.pop(); 
                if (pre != null) { // 中
                    result = Math.min(result, cur.val - pre.val);
                }
                pre = cur;//上一个节点

                cur = cur.right; // 右
            }
        }
        return result;
    }
}

时间复杂度:O(n);(遍历整棵树)

空间复杂度:O(n);(递归栈的空间)


Leetcode 501.二叉搜索树中的众数

题目链接:501.二叉搜索树中的众数

大佬视频讲解:二叉搜索树中的众数视频讲解

个人思路

又是二叉搜索树,所以可以使用中序遍历使得遍历顺序为递增顺序,这样比较出现频率就可以和相邻的值比较(比较时可以使用pre指针和cur指针),最后就把出现频率最高的元素输出;

解法
递归法

这道题只需要遍历一次就可以找到所有的众数。

在遍历时,如果 频率count 等于 maxCount(最大频率),把这个元素加入到结果集中;频率count 大于 maxCount的时候,不仅要更新maxCount,而且要清空结果集,因为结果集之前的元素都失效了。

class Solution {
    ArrayList<Integer> resList;//结果集
    int maxCount;//最大出现频次
    int count;//当前节点频次
    TreeNode pre;//用来比较节点值是否相同

    public int[] findMode(TreeNode root) {
        resList = new ArrayList<>();
        maxCount = 0;
        count = 0;
        pre = null;//初始为空
        findMode1(root);
        int[] res = new int[resList.size()];
        for (int i = 0; i < resList.size(); i++) {
            res[i] = resList.get(i);
        }
        return res;
    }

    public void findMode1(TreeNode root) {
        if (root == null) {
            return;
        }
        findMode1(root.left);

        int rootValue = root.val;
       
        if (pre == null || rootValue != pre.val) { // 计数
            count = 1;
        } else {
            count++;
        }

        // 更新结果以及maxCount
        if (count > maxCount) {
            resList.clear();//清空失效的结果集
            resList.add(rootValue);//加入新的结果
            maxCount = count;
        } else if (count == maxCount) {
            resList.add(rootValue);
        }
        pre = root;


        findMode1(root.right);
    }
}

时间复杂度:O(n);(最差遍历一遍树)

空间复杂度:O(n);(递归树的高度h,结果集最多为n)

迭代法

使用栈模拟递归,

class Solution {
    public int[] findMode(TreeNode root) {
        TreeNode pre = null;
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> result = new ArrayList<>();
        int maxCount = 0;
        int count = 0;
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {

            if (cur != null) {
                stack.push(cur);
                cur =cur.left;//左
            }else {
                cur = stack.pop();//中

                // 计数
                if (pre == null || cur.val != pre.val) {
                    count = 1;
                }else {
                    count++;
                }

                // 更新结果
                if (count > maxCount) {
                    maxCount = count;
                    result.clear();
                    result.add(cur.val);
                }else if (count == maxCount) {
                    result.add(cur.val);
                }
                pre = cur;

                cur = cur.right;//右
            }
        }
        //列表转数组,即result 列表中所有 Integer 元素转换为原始整数值的 int 类型数组。
        return result.stream().mapToInt(Integer::intValue).toArray();
        
    }
}

时间复杂度:O(n);(遍历整棵树)

空间复杂度:O(n);(使用栈,结果集大小)


Leetcode 236. 二叉树的最近公共祖先

题目链接:236. 二叉树的最近公共祖先

大佬视频讲解:二叉树的最近公共祖先视频讲解

个人思路

思路不清晰,主要是如何递归不太清楚。

解法
递归法

首先确定采用后序遍历,因为是需要找出公共祖先,所以先遍历左右节点,然后递归三步走

1.确定递归函数返回值以及参数

需要递归函数返回值,来说明是否找到节点q或者p,那么返回值为bool类型就可以了。

还要返回最近公共节点,可以利用上题目中返回值是TreeNode * ,那么如果遇到p或者q,就把q或者p返回,返回值不为空,就说明找到了q或者p。

2.确定终止条件

遇到空的话,因为树都是空了,所以返回空。

如果 root == q,或者 root == p,说明找到 q p ,则将其返回

3.确定单层递归逻辑

如果递归函数有返回值,搜索一条边和搜索整个树是有区别

搜索一条边的写法:

if (递归函数(root->left)) return ;

if (递归函数(root->right)) return ;

搜索整个树写法:

left = 递归函数(root->left);  // 左
right = 递归函数(root->right); // 右
left与right的逻辑处理;         // 中 

在递归函数有返回值的情况下:如果要搜索一条边,递归函数返回值不为空的时候,立刻返回,如果搜索整个树,直接用一个变量left、right接住返回值,这个left、right后续还有逻辑处理的需要,也就是后序遍历中处理中间节点的逻辑(也是回溯

在这道题中,还要遍历根节点右子树(即使此时已经找到了目标节点了),因为要等left与right逻辑处理完之后才能返回。

其中处理left和right的逻辑如下:

如果left 和 right都不为空,说明此时root就是最近公共节点。

如果left为空,right不为空,就返回right,说明目标节点是通过right返回的,反之依然。如下图

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || 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) { // 若未找到节点 p 或 q
            return null;
        }else if(left == null && right != null) { // 若找到一个节点
            return right;
        }else if(left != null && right == null) { // 若找到一个节点
            return left;
        }else { // 若找到两个节点
            return root;
        }
    }
}

时间复杂度:O(n);(遍历二叉树)

空间复杂度:O(n);(递归树的高度,如果是一个高度不平衡的树(例如链状结构)高度与n接近)


以上是个人的思考反思与总结,若只想根据系列题刷,参考卡哥的网址代码随想录算法官网

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

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

相关文章

CVE-2019-5782:kArgumentsLengthType 设置偏小导致优化阶段可以错误的去除 CheckBound 节点

文章目录 环境搭建漏洞分析笔者初分析笔者再分析漏洞触发源码分析 漏洞利用总结 环境搭建 sudo apt install pythongit reset --hard b474b3102bd4a95eafcdb68e0e44656046132bc9 export DEPOT_TOOLS_UPDATE0 gclient sync -D// debug version tools/dev/v8gen.py x64.debug ni…

分布式调用与高并发处理(二)| Dubbo

文章目录 Dubbo概念_什么是分布式系统单机架构集群架构分布式架构单机、集群和分布式的区别 Dubbo概念_什么是RPCRPC两个作用&#xff1a;常见 RPC 技术和框架&#xff1a; Dubbo概念_简介Dubbo能做什么Dubbo支持的协议 Dubbo概念_核心组件注册中心Registry服务提供者Provider服…

Cartwheel——文本生成3D动作或动画的工具

一个强大的文本转3D动画平台,用户只需通过输入文字提示即可生成视频、游戏、电影、广告、社交或VR项目所需的3D动画角色。 Cartwheel 是一个功能强大的文本到动画平台。只需键入即可为您的视频、游戏、电影、广告、社交或 VR 项目制作角色动画 定位: 定位于为用户提供简单…

Java学习笔记(13)

阶段项目 拼图小游戏 JFrame JMenuBar JMenu JMenuItem 用add方法添加到不同的对象中 添加图片 先创建一个图片ImageIcon的对象&#xff0c;写入图片的路径 再创建JLabel管理容器对象&#xff0c;把图片放到这个容器中&#xff0c;再把容器添加到界面 界面坐标位置 改变图…

MySQL数据导入的方式介绍

MySQL数据库中的数据导入是一个常见操作&#xff0c;它涉及将数据从外部源转移到MySQL数据库表中。在本教程中&#xff0c;我们将探讨几种常见的数据导入方式&#xff0c;包括它们的特点、使用场景以及简单的示例。 1. 命令行导入 使用MySQL命令行工具mysql是导入数据的…

pycharm @NotNull parameter ‘module‘ of ...

下载了最新pycharm &#xff0c;无法启动运行 pycharm或者idea中Run/Debug Python项目报错 Argument for NotNull parameter ‘module‘ of … 解决方案 删除项目根目录的 idea 文件夹 随后重启&#xff0c;重新配置即可

vue项目中使用highcharts记录(甘特图)

使用npm添加到项目中&#xff1a; npm install highcharts npm install highcharts-vue// 我在实际使用时用上面两条命令安装后&#xff0c;引入时会报错 // 所以按照下面的示例中的版本安装的指定版本(vue版本为2.6.14)npm install highcharts7.1.3 npm install highchart…

计算机考研|跨专业考408到底有多难?

在就是说&#xff0c;敢跨专业考研的&#xff0c;都是狠人 为什么这么说&#xff0c;因为考研备考最多也就一年的时间&#xff0c;然后还要处理自己本专业的事情&#xff0c;还要学习心得&#xff0c;从来没有接触过的专业课&#xff0c;那真的就是抓瞎啊。这绝对要很强的时间…

【刷题训练】Leetcode415.字符串相加

字符串相加 题目要求 示例 1&#xff1a; 输入&#xff1a;num1 “11”, num2 “123” 输出&#xff1a;“134” 示例 2&#xff1a; 输入&#xff1a;num1 “456”, num2 “77” 输出&#xff1a;“533” 示例 3&#xff1a; 输入&#xff1a;num1 “0”, num2 “0”…

二、HarmonyOS 操作系统以及相关生态

前言 2019年8月9日&#xff0c;华为技术有限公司在华为开发者大会上正式发布了HarmonyOS 1.0&#xff0c;同时宣布该操作系统源代码开源。 2020年9月10日&#xff0c;HarmonyOs 2.0正式发布。与HarmonyOs 1.0版本相比&#xff0c;HarmonyOs 2.0在分布式软总线、分布式数据管理、…

智慧公厕——旅游景区的高端必备设施

随着旅游行业的迅猛发展&#xff0c;越来越多的人选择在假期中出游&#xff0c;寻找美好的旅行体验。而一个良好的旅游景区必须拥有完善的基础设施&#xff0c;其中智慧公厕则是不可或缺的一环。智慧公厕源头厂家广州中期科技有限公司&#xff0c;已经打造了大量精品工程&#…

JVMJava虚拟机

JVM的内存区域 程序计数器&#xff1a; 字节码解释器通过改变程序计数器来依次读取指令&#xff0c;从而实现代码的流程控制&#xff0c;如&#xff1a;顺序执行、选择、循环、异常处理。 在多线程的情况下&#xff0c;程序计数器用于记录当前线程执行的位置&#xff0c;从而当…

01——LenNet网络结构,图片识别

目录 1、model.py文件 &#xff08;预训练的模型&#xff09; 2、train.py文件&#xff08;会产生训练好的.th文件&#xff09; 3、predict.py文件&#xff08;预测文件&#xff09; 4、结果展示&#xff1a; 1、model.py文件 &#xff08;预训练的模型&#xff09; impor…

Day17 深入类加载机制

Day17 深入类加载机制 文章目录 Day17 深入类加载机制一、初识类加载过程二、深入类加载过程三、利用类加载过程理解面试题四、类加载器五、类加载器分类六、类加载器之间的层次关系七、双亲委派模型 - 概念八、双亲委派模型 - 工作过程九、双亲委派模型 - 好处十、双亲委派原则…

Jmeter---分布式

分布式&#xff1a;多台机协作&#xff0c;以集群的方式完成测试任务&#xff0c;可以提高测试效率。 分布式架构&#xff1a;控制机&#xff08;分发任务&#xff09;与多台执行机&#xff08;执行任务&#xff09; 环境搭建&#xff1a; 不同的测试机上安装 Jmeter 配置基…

Sparse Convolution 讲解

文章目录 1. 标准卷积与Sparse Conv对比(1)普通卷积(2) 稀疏卷积(3) 改进的稀疏卷积(subm)2 Sparse Conv 官方API3. Sparse Conv 计算3. 1 Sparse Conv 计算流程3. 2 案例3.2.1 普通稀疏卷积3.2.2 subm模式的稀疏卷积3D点云数据非常稀疏,尤其体素化处理后(比如200k的点放…

【算法篇】七大基于比较的排序算法精讲

目录 排序 1.直接插入排序 2.希尔排序 3.直接选择排序 4.堆排序 5.冒泡排序 6.快速排序 7.归并排序 排序 排序算法的稳定性&#xff1a;假设在待排序的序列中&#xff0c;有多个相同的关键字&#xff0c;经过排序后&#xff0c;这些关键字的先后顺序不发生改变&#…

Spring项目问题—前后端交互:Method Not Allowed

问题 前后端交互时出现Method Not Allowed问题 Ajax中使用的是get&#xff0c;方法仍然出现post方法报错 Resolved [org.springframework.web.HttpRequestMethodNotSupportedException: Request method POST not supported] 浏览器中没有报错&#xff0c;只是接收不到后端返…

解锁数据潜力:OceanBase国产数据库学习不容错过的秘密!

介绍&#xff1a;OceanBase是一款由阿里巴巴和蚂蚁金服自主研发的通用分布式关系型数据库&#xff0c;它专为企业级应用而设计&#xff0c;具有金融级别的可靠性。以下是对OceanBase的详细介绍&#xff1a; 高可用性&#xff1a;OceanBase通过实现Paxos多数派协议和多副本特性&…

MySql入门教程--MySQL数据库基础操作

꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好&#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解&#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN …
最新文章