二叉搜索树题目:二叉搜索树的最小绝对差

2024-02-12 22:12

本文主要是介绍二叉搜索树题目:二叉搜索树的最小绝对差,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
  • 解法一
    • 思路和算法
    • 代码
    • 复杂度分析
  • 解法二
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

标题:二叉搜索树的最小绝对差

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

难度

3 级

题目描述

要求

给定一个二叉搜索树的根结点 root \texttt{root} root,返回树中任意两个不同结点值之间的差值绝对值的最小值。

示例

示例 1:

示例 1

输入: root = [4,2,6,1,3] \texttt{root = [4,2,6,1,3]} root = [4,2,6,1,3]
输出: 1 \texttt{1} 1

示例 2:

示例 2

输入: root = [1,0,48,null,null,12,49] \texttt{root = [1,0,48,null,null,12,49]} root = [1,0,48,null,null,12,49]
输出: 1 \texttt{1} 1

数据范围

  • 树中结点数目在范围 [2, 10 4 ] \texttt{[2, 10}^\texttt{4}\texttt{]} [2, 104]
  • 0 ≤ Node.val ≤ 10 5 \texttt{0} \le \texttt{Node.val} \le \texttt{10}^\texttt{5} 0Node.val105

解法一

思路和算法

由于二叉搜索树的中序遍历序列是单调递增的,因此只要得到二叉搜索树的中序遍历序列,然后计算序列中的每一对相邻结点值之差的绝对值,其中的最小值即为任意两个不同结点值之间的差值绝对值的最小值。

由于只是计算二叉搜索树的中序遍历序列中的每一对相邻结点值之差的绝对值,因此不需要存储完整的中序遍历序列,而是只需要存储上一个遍历到的结点值。每次访问结点时,当前结点值一定大于上一个结点值,因此计算当前结点值与上一个结点值之差,即为相邻结点值之差的绝对值。遍历结束之后,即可得到任意两个不同结点值之差的绝对值的最小值。

代码

class Solution {public int getMinimumDifference(TreeNode root) {int minDiff = Integer.MAX_VALUE;Deque<TreeNode> stack = new ArrayDeque<TreeNode>();int prev = Integer.MIN_VALUE / 10;TreeNode node = root;while (!stack.isEmpty() || node != null) {while (node != null) {stack.push(node);node = node.left;}node = stack.pop();minDiff = Math.min(minDiff, node.val - prev);prev = node.val;node = node.right;}return minDiff;}
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉搜索树的结点数。每个结点都被访问一次。

  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉搜索树的结点数。空间复杂度主要是栈空间,取决于二叉搜索树的高度,最坏情况下二叉搜索树的高度是 O ( n ) O(n) O(n)

解法二

思路和算法

解法一虽然不需要存储中序遍历序列,但是仍需要使用栈空间。使用莫里斯遍历可以将空间复杂度降低到 O ( 1 ) O(1) O(1)

遍历过程中维护上一个结点值。每次访问结点时,计算当前结点值与上一个结点值之差。遍历结束之后,即可得到任意两个不同结点值之差的绝对值的最小值。

代码

class Solution {public int getMinimumDifference(TreeNode root) {int minDiff = Integer.MAX_VALUE;int prev = Integer.MIN_VALUE / 10;TreeNode node = root;while (node != null) {if (node.left == null) {minDiff = Math.min(minDiff, node.val - prev);prev = node.val;node = node.right;} else {TreeNode predecessor = node.left;while (predecessor.right != null && predecessor.right != node) {predecessor = predecessor.right;}if (predecessor.right == null) {predecessor.right = node;node = node.left;} else {predecessor.right = null;minDiff = Math.min(minDiff, node.val - prev);prev = node.val;node = node.right;}}}return minDiff;}
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉搜索树的结点数。使用莫里斯遍历,每个结点最多被访问两次。

  • 空间复杂度: O ( 1 ) O(1) O(1)

这篇关于二叉搜索树题目:二叉搜索树的最小绝对差的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/703731

相关文章

搜索题解

单词方阵 - 洛谷 思路:在字符方阵中找到y并将其坐标存入数组,再找其八个方向是否有目标字符,有的话就深搜一个方向,能搜完就将数组标记,最好标记的就输入字符,没标记的就输出*。 代码如下: #include<stdio.h>int next1[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};char s[8]={

【递归搜索回溯专栏】前言与本专栏介绍

本专栏内容为:递归,搜索与回溯算法专栏。 通过本专栏的深入学习,你可以了解并掌握算法。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:递归搜索回溯专栏 🚚代码仓库:小小unicorn的代码仓库🚚 🌹🌹🌹关注我带你学习编程知识 前言 递归什么是递归为什么会用到递归如何理解递归怎样写好递归 搜索深度优先/宽度优先关系图拓展搜索 回溯与剪枝 递归

为什么网站页面没有被百度搜索收录?是网站被攻击了?

例如,为什么网站页面没有被百度搜索收录? 网站是否受到攻击? 网站索引量和网站流量之间有关系吗? 您在运行网站或小程序时是否有过这样的疑问? 下面我将为大家详细解答这些问题。 1.PC/H5站点相关 1、为什么新网站页面长时间不收录? 百度搜索收录网页是有一定期限的。 如果是对用户有价值的页面,收录期间百度搜索肯定会收录。 如果您发现页面内容长时间没有被百度搜索收录,建议检查页面内容是否

LeetCode240题:搜索二维矩阵II(python3)

代码思路: “根节点” 对应的是矩阵的 “左下角” 和 “右上角” 元素,以 matrix 中的左下角元素为标志数 flag ,则有: 若 flag > target ,则 target 一定在 flag 所在行的上方 ,即 flag 所在行可被消去,i– 若 flag < target ,则 target 一定在 flag 所在 列的右方 ,即 flag 所在列可被消去,j++ 算法流程: 从

C/C++训练1---最大公约数与最小公倍数 (sdut oj)

C/C++训练1---最大公约数与最小公倍数 Time Limit: 1000MS  Memory Limit: 65536KB Problem Description 输入两个整数,求它们的最大公约数与最小公倍数。 Input 输入两个整数,两个整数之间用空格分开。 Output 第一行输出最大公约数; 第二行

软件设计师软考题目解析12 --每日五题

想说的话:要准备软考了。0.0,其实我是不想考的,但是吧,由于本人已经学完所有知识了,只是被学校的课程给锁在那里了,不然早找工作去了。寻思着反正也无聊,就考个证玩玩。        本人github地址:nanshaws (cover) (github.com)        各位想学习的,可以在上面联系我。 目录 题一 题二 题三 题四 题五 总结 题一

试画出一张表以说明Z*11中每个元素的阶。找出最小的原根g并计算出一张表,要求写出对所有x属于Z*11,相应的ind11,g(x)的值。

《算法导论》练习31.6-1   ord11(1) = 1 ord11(2) = 10 ord11(3) = 5 ord11(4) = 5 ord11(5) = 5 ord11(6) = 10 ord11(7) = 10 ord11(8) = 10 ord11(9) = 5 ord11(10) = 2   因此最小原根是g=2   ind11,2(1) = 0 in

机器学习学习笔记(5)----测试最小二乘法

上一篇文章中《机器学习学习笔记(4)----线性回归的数学解析》,求最优的w的方法是普通最小二乘法(Ordinary Least Squares,OLS),最小二乘法的python实现相对简单(ols.py): import numpy as npclass OLSLinearRegression:def _ols(self, X, y):'''最小二乘法'''tmp = np.linalg.i

网络流算法集合 EK dinic 最小费用最大流 (Dijkstra实现)

终于快把网络流的模板写完了,先贴几个,存边用前向星实现,既保证了速度又免去了写链表的麻烦,代码绝对是你能找到的代码中最精简的 //EK#include<stdio.h>#include<iostream>using namespace std;#include<memory.h>#define MAXN 300#define MAXFLOW 2000000000int n,s,t,m,flow[

浅谈ACM ICPC的题目风格和acm比赛近几年, 恩。。。看看吧,了解一下~~

ACM ICPC的比赛形式一般是五个小时八个题目,综合考察选手的数学能力、算法能力、coding能力和debug能力,还有团队配合能力。数学方面主要强调组合数学、图论和数论这三个方面的能力;而算法的覆盖范围很广,涉及了大部分经典的算法,和少量较前沿的算法。由于每道题目都需要通过所有的测试数据才能得分,并且需要精确解,这限制了Approximation algorithm在一些NP-hard的题目中