算法训练营第二十一天(二叉树part7)

算法训练营第二十一天(二叉树part7)

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

力扣题目链接(opens new window)

题目

给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。

示例:

在这里插入图片描述

提示:树中至少有 2 个节点。

解答

方法一

利用搜索树的特性,使用中序放入数组中,数组一定是递增序列,最小的一定是相邻的两个的差值

//递归法
class Solution {
    public int getMinimumDifference(TreeNode root) {
		List<Integer> results = new ArrayList<>();//递增序列
		travel(root,results);
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < results.size() - 1; i++) {
			min = Math.min(min,Math.abs(results.get(i) - results.get(i + 1)));
		}
		return min;
    }
	private void travel(TreeNode cur,List<Integer> results){
		if (cur == null)
			return;
		travel(cur.left,results);

		results.add(cur.val);

		travel(cur.right,results);
	}
}

//迭代法
class Solution {

    public int getMinimumDifference(TreeNode root) {
		List<Integer> results = new ArrayList<>();//递增序列
		Stack<TreeNode> stack = new Stack<>();
		while (root != null || !stack.isEmpty()){
			while (root != null){
				stack.push(root);
				root = root.left;
			}
			//此时栈顶是最左侧的子树的根节点,每一次循环如果没有右子树就会进行一次回溯
			TreeNode cur = stack.pop();
			results.add(cur.val);

			root = cur.right;
		}

		int min = Integer.MAX_VALUE;
		for (int i = 0; i < results.size() - 1; i++) {
			min = Math.min(min,Math.abs(results.get(i) - results.get(i + 1)));
		}
		return min;
    }
}
方法二:双指针(推荐)
class Solution {
	int result = Integer.MAX_VALUE;
	TreeNode pre;
    public int getMinimumDifference(TreeNode root) {
		travel(root);
		return result;
    }
	private void travel(TreeNode cur){
		if (cur == null)
			return;

		travel(cur.left);

		if (pre != null)
			result = Math.min(result,Math.abs(cur.val - pre.val));
		pre = cur;

		travel(cur.right);
	}
}

在这里插入图片描述

  1. travel(cur.left);在最后一次跳出循环时,此时cur指向最左侧的1,而pre指向null
  2. 接下来进行,pre指向这一轮的cur,即1
  3. 然后travel(cur.right);,同样为空
  4. cur=1这一轮结束,然后进行回溯,此时这一轮的cur指向4,因为跳出了上一层递归,而pre指向上一轮的cur即1

501.二叉搜索树中的众数

力扣题目链接(opens new window)

题目

给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。

假定 BST 有如下定义:

  • 结点左子树中所含结点的值小于等于当前结点的值
  • 结点右子树中所含结点的值大于等于当前结点的值
  • 左子树和右子树都是二叉搜索树

例如:

给定 BST [1,null,2,2],

在这里插入图片描述

返回[2].

提示:如果众数超过1个,不需考虑输出顺序

进阶:你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)

解答

常规做法(没使用搜索树的特性,不推荐)
class Solution {
    public int[] findMode(TreeNode root) {
		Map<Integer,Integer> map = new HashMap<>();
		travel(root,map);
		List<Map.Entry<Integer, Integer>> sortedEntries = new ArrayList<>(map.entrySet());
		sortedEntries.sort((entry1, entry2) -> entry2.getValue().compareTo(entry1.getValue()));//降序
		List<Integer> result = new ArrayList<>();
		int count = sortedEntries.get(0).getValue();
		for (Map.Entry<Integer, Integer> sortedEntry : sortedEntries) {
			if (sortedEntry.getValue() == count)
				result.add(sortedEntry.getKey());
			else
				break;
		}

		// 转换为 Integer[]
		Integer[] arr = result.toArray(new Integer[0]);
		// 再转换为 int[]
		int[] intArr = Arrays.stream(arr).mapToInt(Integer::intValue).toArray();
		return intArr;
    }

	private void travel(TreeNode root,Map<Integer,Integer> map){
		if (root == null)
			return;
		travel(root.left,map);
		map.put(root.val,map.getOrDefault(root.val,0) + 1);
		travel(root.right,map);
	}
}
使用搜索树特性(双指针)

不使用额外空间,还是使用递归,但是由于是搜索树,所以如果使用中序只要是相同的数一定会相邻,那么如果达到最大的count就放入,如果比最大的count还大,就清空列表,重新放入

必须是双指针,不然一个指向左子树,另一个找不到根

class Solution {
	ArrayList<Integer> results;
	int maxCount;
	int count;
	TreeNode pre;
    public int[] findMode(TreeNode root) {
		results = new ArrayList<>();
		maxCount = 0;
		count = 0;
		pre = null;
		travel(root);
		int[] result = new int[results.size()];
		for (int i = 0; i < results.size(); i++) {
			result[i] = results.get(i);
		}
		return result;
    }

	private void travel(TreeNode cur){
		if (cur == null)
			return;

		travel(cur.left);

		if (pre != null && pre.val == cur.val)
			count++;
		else
			count = 1;
		pre = cur;

		if (count == maxCount)
			results.add(cur.val);
		if (count > maxCount){
			results.clear();
			maxCount = count;
			results.add(pre.val);
		}

		travel(cur.right);
	}
}

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

力扣题目链接(opens new window)

题目

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

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

例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

在这里插入图片描述

示例 1: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出: 5 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉树中。

解答

后序

情况1:p与q分别在左右子树

在这里插入图片描述

情况2:一个在左右子树,一个在根

		if (root == p || root == q)
			return root;//满足第二种情况
//该代码解决了情况二

在这里插入图片描述

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return travel(root, p, q);
    }

	private TreeNode travel(TreeNode root, TreeNode p, TreeNode q){
		if (root == null)
			return null;
		if (root == p || root == q)
			return root;//满足第二种情况

		TreeNode left = travel(root.left,p,q);
		TreeNode right = travel(root.right,p,q);

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

eNode right = travel(root.right,p,q);

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

}


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

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

相关文章

原来进制题如此简单

进制相关 二进制数与其他进制数之间的转化 二进制数转其他进制数&#xff08;十进制数除外&#xff09;一般不能直接转化&#xff0c;一般需要过度至十进制数&#xff0c;再转化为其他进制数。同理&#xff0c;其他进制数&#xff08;十进制数除外&#xff09;转二进制数也需过…

flutter多入口点entrypoint

native中引擎对象本身消耗内存(每个引擎对象约莫消耗42MB内存) 多引擎&#xff1a;native多引擎>启动>flutter多入口点entrypoint>多main函数>多子包元素集>多(子)程序 单引擎(复用)&#xff1a;native单引擎>复用启动>flutter多入口点entrypoint>多m…

error:LNK2005 已经在*.obj中定义 的原因分析及对策

LNK2005是一个重复定义错误&#xff0c;造成LNK2005主要有以下几种情况&#xff1a; 目录 全局变量的重复定义 情况A&#xff1a;全局变量在.cpp文件中的多次声明 情况B&#xff1a;变量名重复 头文件的包含重复 解决方案 #ifndef标识符宏定义 pragma once预编译 头文件…

使用yml文件配置python日志

新建一个logging.yml文件&#xff0c;内容如下&#xff1a; logging库提供了多个组件&#xff1a;Logger、Handler、Filter、Formatter&#xff1a; Logger 对象提供应用程序可直接使用的接口&#xff0c;供应用代码使用&#xff1b; Handler 发送日志到适当的目的地&#xff…

PMC管理中落实生产作业计划的思路与方法

在快节奏的现代商业环境中&#xff0c;PMC&#xff08;生产及物料控制&#xff09;管理对于确保企业生产流程的高效运转至关重要。生产作业计划的落实不仅关乎企业的生产效率和成本控制&#xff0c;更是企业竞争力的重要体现。那么&#xff0c;PMC管理中如何有效落实生产作业计…

上传应用程序到苹果应用商店的工具和要点

引言 在今天的移动应用市场中&#xff0c;将应用程序上传到苹果应用商店&#xff08;App Store&#xff09;是许多开发者的首要任务之一。然而&#xff0c;不同操作系统下的开发者可能需要使用不同的工具和遵循不同的要求来完成这一任务。本文将介绍在 macOS、Windows 和 Linu…

【C语言】:字符函数和字符串函数

这里写目录标题 1、strlen的使用和模拟实现2、strcpy的使用和模拟3、strcat 的使用和模拟实现4、strcmp 的使用和模拟实现5、strncpy 函数的使用6、strncat 函数的使用7、strncmp函数的使用8、strstr 的使用和模拟实现9、strtok 函数的使用10、strerror 函数的使用11、字符分类…

独家原创 | SCI 1区 高创新轴承故障诊断模型!

往期精彩内容&#xff1a; Python-凯斯西储大学&#xff08;CWRU&#xff09;轴承数据解读与分类处理 Python轴承故障诊断 (一)短时傅里叶变换STFT Python轴承故障诊断 (二)连续小波变换CWT_pyts 小波变换 故障-CSDN博客 Python轴承故障诊断 (三)经验模态分解EMD_轴承诊断 …

MySQL数据库 数据库基本操作(四):表的增删查改(下)

1. 联合查询 注:联合查询是面试中的重点,只要考到sql,大多数情况下都考的是联合查询,而且联合查询也是我们学习中的难点. 1.1 笛卡尔积 在实际开发中,数据往往来自不同的表,所以要多表联合查询.多表查询是对多张表的数据笛卡尔积. 它们是两张表的各行数据通过全排列得到的. …

摩尔信使MThings之数据网关:Modbus转MQTT

由于现场设备和物联网云平台采用了不同的通信协议&#xff0c;而为了实现它们之间的互操作性和数据交换&#xff0c;需要进行协议转换。 MQTT作为一种轻量级的、基于发布/订阅模式的通信协议&#xff0c;适用于连接分布式设备和传感器网络&#xff0c;而MODBUS协议则常用于工业…

ISG立式管道离心泵(管道增压泵)

一、设计特征 ISG立式管道离心泵是一种高效的水泵&#xff0c;它采用立式单级或多级离心泵的设计&#xff0c;使得电机轴与泵轴直接连接&#xff0c;减少了传输损失。该泵的主要部件包括电机、泵体、叶轮、轴封及泵盖等。与传统卧式泵相比&#xff0c;ISG泵占地面积小&#xff…

像用户一样测试:别掉链子

“掉链子”是一句俗语&#xff0c;比喻在关键时刻出故障&#xff0c;或者重要的事情本该做好却没做好。 “掉链子”的说法来自于自行车&#xff1a;在骑行过程中&#xff0c;链条通过链轮传送&#xff0c;带动车轮滚滚向前。当链条从链轮上脱落&#xff0c;就无法进行传动&…

k8s部署efk

环境简介&#xff1a; kubernetes: v1.22.2 helm&#xff1a; v3.12.0 elasticsearch&#xff1a; 8.8.0 chart包&#xff1a;19.10.0 fluentd: 1.16.2 chart包&#xff1a; 5.9.4 kibana: 8.2.2 chart包&#xff1a;10.1.9 整体架构图&#xff1a; 一、Elasticsearch安装…

跨境电商选品思路:12个方法和爆品法则(完结篇)

不管你是做亚马逊、速卖通、Shopee 、Lazada、美客多、eBay、SHEIN、Temu、Tiktok、shopify等跨境电商平台的卖家&#xff0c;选品思路一定要清楚&#xff0c;选到好品才是成为爆品的基础。店雷达继续给各位跨境商家分享12个大数据选品场景思路&#xff0c;错过其他选品场景思路…

建设智慧公厕有什么好处?@光明源,都有哪些功能?

在城市化进程不断加快的今天&#xff0c;智慧公厕作为城市基础设施的重要组成部分&#xff0c;正逐渐受到各地政府和管理者的重视。那么&#xff0c;建设智慧公厕到底有哪些好处&#xff1f;它们又都涉及哪些功能呢&#xff1f;让我们一起来探讨一下。 首先&#xff0c;建设智…

初学python记录:力扣1600. 王位继承顺序

题目&#xff1a; 一个王国里住着国王、他的孩子们、他的孙子们等等。每一个时间点&#xff0c;这个家庭里有人出生也有人死亡。 这个王国有一个明确规定的王位继承顺序&#xff0c;第一继承人总是国王自己。我们定义递归函数 Successor(x, curOrder) &#xff0c;给定一个人…

基于SpringBoot+Vue+Mysql的图书管理系统

博主介绍&#xff1a; 大家好&#xff0c;本人精通Java、Python、C#、C、C编程语言&#xff0c;同时也熟练掌握微信小程序、Php和Android等技术&#xff0c;能够为大家提供全方位的技术支持和交流。 我有丰富的成品Java、Python、C#毕设项目经验&#xff0c;能够为学生提供各类…

[leetcode]只出现一次的数字Ⅲ

题目&#xff1a; 给你一个整数数组 nums&#xff0c;其中恰好有两个元素只出现一次&#xff0c;其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。 你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。 示例 1&…

Tiktok矩阵系统是什么?——Tiktok矩阵系统的优势、功能、及应用场景的介绍

摘要 Tiktok作为全球现象级的短视频平台,其发展前景日益明朗。 Tiktok全世界有多少用户? TikTok作为全球性的社交媒体平台,其用户数量一直在持续增长。根据最新的数据,预计到2024年,TikTok的用户数量将达到数十亿,覆盖全球范围内的各个年龄段和地区。具体来说,根据Ti…

总结SQL相对常用的几个字符函数

目录 字符的截取 substr() trim()、ltrim()、rtrim() 字符串的拼接 ||、 字符的大小写转换 upper(column_name):大写 lower(column_name):小写 字符替换 replace() 搜索字符 instr(column_name, substring_to_find,start,n_appearence) charindex(substring_to_fi…