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

本文主要是介绍算法打卡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++;}// 更新结果以及maxCountif (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 或 qreturn 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接近)


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

这篇关于算法打卡day18|二叉树篇07|Leetcode 530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数、236. 二叉树的最近公共祖先的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj1330(LCA最近公共祖先)

题意:求最近公共祖先 思路:之前学习了树链剖分,然后我就用树链剖分的一小部分知识就可以解这个题目了,记录每个结点的fa和depth。然后查找时,每次将depth大的结点往上走直到x = y。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO