代码随想录算法训练营第二十一天|530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数、236. 二叉树的最近公共祖先

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

题目链接:530.二叉搜索树的最小绝对差
文档讲解:代码随想录
状态:还可以

思路:使用中序遍历来遍历二叉搜索树。在中序遍历过程中,比较当前节点和前驱节点的值,更新最小差值。返回二叉搜索树中任意两个节点值的最小差值。

递归:

int min = Integer.MAX_VALUE;
// 前驱节点
TreeNode pre;

public int getMinimumDifference(TreeNode root) {
    // 如果当前节点为空,返回0
    if (root == null) {
        return 0;
    }
    // 递归遍历左子树
    getMinimumDifference(root.left);
    
    // 如果前驱节点不为空,计算当前节点和前驱节点的值差
    if (pre != null) {
        int dif = root.val - pre.val;
        // 更新最小差值
        min = Math.min(min, dif);
    }
    // 更新前驱节点为当前节点
    pre = root;
    
    // 递归遍历右子树
    getMinimumDifference(root.right);
    // 返回最小差值
    return min;
}

迭代:

public int bfs(TreeNode root) {
    // 使用双端队列模拟栈
    Deque<TreeNode> stack = new LinkedList<>();
    // 初始化前驱节点值为最大整数
    int pre = Integer.MAX_VALUE;
    // 初始化最小差值为一个很大的数值
    int min = Integer.MAX_VALUE;
    
    // 如果根节点为空,返回0
    if (root == null) {
        return 0;
    }
    
    // 将根节点添加到栈中
    stack.addLast(root);
    
    // 当栈不为空时,继续遍历
    while (!stack.isEmpty()) {
        // 弹出栈顶元素
        TreeNode node = stack.pollLast();
        
        if (node != null) {
            // 先处理右子树
            if (node.right != null) {
                stack.addLast(node.right);
            }
            // 中间节点处理两次,设置一个null标记
            stack.addLast(node);
            stack.addLast(null);
            // 再处理左子树
            if (node.left != null) {
                stack.addLast(node.left);
            }
        } else {
            // 第二次遇到中间节点,进行实际处理
            node = stack.pollLast();
            // 计算当前节点与前驱节点的差值,并更新最小差值
            min = Math.min(Math.abs(node.val - pre), min);
            // 更新前驱节点的值
            pre = node.val;
        }
    }
    // 返回最小差值
    return min;
}

501.二叉搜索树中的众数

在这里插入图片描述

题目链接:501.二叉搜索树中的众数
文档讲解:代码随想录
状态:还行,能做出来,虽然不是最优解

思路:通过中序遍历二叉搜索树,在遍历过程中统计每个节点值的出现次数,并找到出现次数最多的节点值。

题解:

public class FindMode {
    // 存储众数的列表
    List<Integer> list = new LinkedList<>();

    public int[] findMode(TreeNode root) {
        // 调用 getCount 方法遍历二叉树并找到众数
        getCount(root);
        
        // 将 list 转换为数组
        int[] res = new int[list.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    // 前一个节点的值,初始值为最小整数
    int preVal = Integer.MIN_VALUE;
    // 当前值出现的次数
    int count = 0;
    // 最大出现次数
    int max = Integer.MIN_VALUE;

    public void getCount(TreeNode root) {
        if (root == null) {
            return;
        }
        // 递归遍历左子树
        getCount(root.left);
        
        // 如果当前节点值等于前一个节点值,增加计数
        if (preVal == root.val) {
            count += 1;
        } else {
            // 如果当前节点值不等于前一个节点值,重置计数
            count = 1;
        }
        
        // 如果当前计数大于最大计数,清空列表并更新最大计数
        if (count > max) {
            list.clear();
            max = count;
            list.add(root.val);
        } else if (count == max) {
            // 如果当前计数等于最大计数,将当前值加入列表
            list.add(root.val);
        }
        
        // 更新前一个节点值为当前节点值
        preVal = root.val;
        
        // 递归遍历右子树
        getCount(root.right);
    }

}

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

在这里插入图片描述

题目链接:236. 二叉树的最近公共祖先
文档讲解:代码随想录
状态:想到使用后序遍历,但是判断逻辑没想出来(只想到true或false判断是否包含p,q,没想到使用返回节点和null来代替)

思路:使用后序遍历可以先获取左右子树的信息,然后利用左右子树信息和p,q比较从而实现判断逻辑。

题解:

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果根节点为空或根节点是p或q之一,则直接返回根节点
        if (root == null || root == p || root == q) {
            return root;
        }

        // 在左子树中查找最近公共祖先
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 在右子树中查找最近公共祖先
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 如果p和q分别在当前根节点的左右子树中,则当前根节点是最近公共祖先
        if (left != null && right != null) {
            return root;
        }

        // 如果左子树中找到了p或q(即left不为空),返回left
        if (left != null) {
            return left;
        }

        // 如果右子树中找到了p或q(即right不为空),返回right
        if (right != null) {
            return right;
        }

        // 如果左右子树中都没有找到p或q,返回null
        return null;
    }

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

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

相关文章

中国四大高原矢量示意图分享

我们在《中国地势三级阶梯示意图分享》一文中&#xff0c;为你分享了中国三级阶梯示意图的矢量文件。 现在&#xff0c;我们再为你分享中国四大高原的矢量示意图文件&#xff0c;你可以在文末查看文件的领取方法。 我国四大高原是如何划分的&#xff1f; 中国四大高原分别为…

你觉得前端开发人员有必要学习Rust吗?

有必要&#xff0c;为什么&#xff1f; 1. 性能优势 Rust能编译成高效的机器码&#xff0c;这对于需要高性能处理的前端项目尤其有利。例如&#xff0c;处理复杂的数据计算或图像处理时&#xff0c;Rust可以提供接近于C/C的性能&#xff0c;同时避免诸如内存泄漏或缓冲区溢出…

2024中国网络安全产品用户调查报告(发布版)

自2020年始&#xff0c;人类进入了21世纪的第二个十年&#xff0c;全球进入了百年未有之大变局&#xff0c;新十年的开始即被新冠疫情逆转了全球化发展的历程&#xff0c;而至2022年3月俄乌战争又突然爆发&#xff0c;紧接着2023年7月“巴以冲突"皱起&#xff0c;世界快速…

LabVIEW进行负载测试

本文介绍了如何使用LabVIEW进行负载测试&#xff0c;通过一个具体案例详细讲解了测试系统的组成、工作原理和实现方法。系统采用先进的硬件和软件架构&#xff0c;结合LabVIEW的强大功能&#xff0c;成功实现了对设备的高效负载测试&#xff0c;确保了系统的可靠性和性能。 项…

LogicFlow 学习笔记——1. 初步使用 LogicFlow

什么是 LogicFlow LogicFlow 是一个开源的前端流程图编辑器和工作流引擎&#xff0c;旨在帮助开发者和业务人员在网页端创建、编辑和管理复杂的业务流程和工作流。它提供了一个直观的界面和强大的功能&#xff0c;使得设计和管理工作流变得更加高效和便捷。 官网地址&#xff…

时间轴、流程类时间轴绘制

效果图 可控制是否绘制在中间控制绘制的线条是否为虚线控制第一条数据圆顶部线条和最后一条数据圆底部线条是否绘制 除了gif图片展示的属性&#xff0c;还可以控制圆的大小颜色、圆是否有上和左偏移、线条颜色等属性 除了通用的时间轴绘制&#xff0c;我们还可以通过改变绘制…

国外创意二维码应用:飞利浦旧物翻新活动,传播可持续性消费的重要性!

你知道去年有超过1000万件礼物被扔进了垃圾场吗? 这些被丢弃的物品中有许多仍在使用&#xff0c;飞利浦希望改变这种浪费现象。 去年的地球日&#xff0c;飞利浦策划了一场名为“Better than New” 的二维码营销活动。他们发布了一个视频&#xff0c;通过这个短视频将所有最终…

微信小程序组件传值

虽然微信小程序是比较轻量的&#xff0c;但是还是拥有组件的 这是文件的基本目录 我们的代码基本都在pages和components文件夹中 在component中创建组件 在component中 &#xff0c;创建一个目录 我创建了一个 head目录 用于配置头部信息 我在这里创建了 一个头部组件&…

Vue基础知识:异步DOM更新是什么?$nextTick是什么?到底应该如何使用。什么是同步?什么是异步?

要先了解异步dom更新是什么就必须先了解&#xff0c;什么是同步&#xff1f;什么是异步&#xff1f; 1.什么是同步&#xff1f;什么是异步&#xff1f; 同步&#xff08;Synchronous&#xff09;&#xff1a; 同步操作是按照代码的顺序执行的&#xff0c;每个操作都必须等待上…

NiceGUI:让Python变身为Web应用开发大师的神器

简介 NiceGUI是一个易于使用的基于Python的UI框架&#xff0c;可以在您的Web浏览器中使用。您可以创建按钮、对话框、Markdown、3D场景、图表等等。 NiceGUI开源支持较好&#xff0c;代码更新频率较高&#xff0c;目前已经更新至: V1.4.26。 适用场景 NiceGUI非常适用于各种…

为什么 JavaScript 在国外逐渐用于前端+后端开发

这个问题其实没人能给出可证伪的结论&#xff0c;那不如干脆给一个感性的答案: 因为阿里“不争气”。 确切的说&#xff0c;因为阿里的nodejs团队没卷赢&#xff0c;至少暂时还没卷赢&#xff0c;没拿到真正有价值的业务场景&#xff0c;做出真正有说服力的案例项目。刚好我有…

【微信小程序】开发环境配置

目录 小程序的标准开发模式&#xff1a; 注册小程序的开发账号 安装开发者工具 下载 设置外观和代理 第一个小程序 -- 创建小程序项目 查看项目效果 第一种&#xff1a;在模拟器上查看项目效果 项目的基本组成结构 小程序代码的构成 app.json文件 project.config…

8.2 Go 导入与导出

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…

手机短信验证码登录

用户需求&#xff1a; 1、用户使用手机号和短信验证码登录系统 2、未注册过的手机号再登录时实现自动注册 3、新注册的账号只有7天的使用时间&#xff0c;过期后不允许进行登录 功能需求&#xff1a; 登录页面设计 图1.手机号登录 【验证码登录】规则说明&#xff1a; …

各类电机数学模型相关公式总结 —— 集成芯片驱动

0、背景技术概述 永磁直流电机&#xff08;PMDC&#xff09;、永磁同步电机&#xff08;PMSM&#xff09;、无刷直流电机&#xff08;BLDC&#xff09;以及混合式两相步进电机在小功率应用场景中多采用集成芯片驱动&#xff08;如二合一、三合一驱动芯片&#xff09;的原因主要…

Linux C语言:函数的基本用法及传参

一、函数的基本用法 1、main函数 int main(int argc, const char * argv[]) { printf("Hello world\n"); return 0; }数据类型 函数名称 (参数) { //.... return 表达式 } 2、函数 函数是一个完成特定功能的代码模块&#xff0c;其程序代码独立&#xff0c;通常要…

使用Python修改word文档中的表格

使用Python编辑word文档中的表格 介绍效果代码代码解析 介绍 使用python修改word文档中的表格。 效果 修改前的word文档&#xff1a; 注意红框中的表格。 修改后的word文档&#xff1a; 表格内容已经修改。 代码 from docx import Document# 加载现有的Word文档 doc D…

electron基础使用

安装以及运行 当前node版本18&#xff0c;按照官网提供操作&#xff0c;npm init进行初始化操作&#xff0c;将index.js修改为main.js&#xff0c;执行npm install --save-dev electron。&#xff08;这里我挂梯子下载成功了。&#xff09;&#xff0c;添加如下代码至package.…

AI办公自动化:用Kimi批量在Excel文件名中加入日期

工作任务&#xff1a;在一个文件夹中所有的Excel文件后面加上一个日期 在Kimi中输入提示词&#xff1a; 你是一个Python编程专家&#xff0c;写一个Python脚本&#xff0c;具体步骤如下&#xff1a; 打开文件夹&#xff1a;F:\AI自媒体内容\AI行业数据分析\投融资 读取里面所…

电商核心技术系列58:电商平台的智能数据分析与业务洞察

相关系列文章 电商技术揭秘相关系列文章合集&#xff08;1&#xff09; 电商技术揭秘相关系列文章合集&#xff08;2&#xff09; 电商技术揭秘相关系列文章合集&#xff08;3&#xff09; 电商核心技术揭秘56&#xff1a;客户关系管理与忠诚度提升 电商核心技术揭秘57:数…