代码随想录算法训练营第二十天| 654.最大二叉树,617.合并二叉树,700.二叉搜索树中的搜索,98.验证二叉搜索树

本文主要是介绍代码随想录算法训练营第二十天| 654.最大二叉树,617.合并二叉树,700.二叉搜索树中的搜索,98.验证二叉搜索树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 题目与题解

654.最大二叉树

题目链接:654.最大二叉树

代码随想录题解:654.最大二叉树

视频讲解:又是构造二叉树,又有很多坑!| LeetCode:654.最大二叉树_哔哩哔哩_bilibili

解题思路:

        构造最大二叉树,递归非常合适。入参是用于构造的数组,返回值是构造结束后的根结点,终止条件是当前结点为空。递归体为:首先遍历数组,找到数组中最大值及其所在的位置;然后定义两个新数组,一个包含最大值左边所有数,用于构造左子树,一个包含最大值右边所有数,用于构造右子树;然后分别将两个数组输入最大二叉树构造方法,构造对应根结点的左右子树。

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {if (nums.length == 0) return null;int maxIndex = 0;int max = nums[0];for (int i = 1; i < nums.length; i++) {if (nums[i] > max) {maxIndex = i;max = nums[i];}}int[] leftNums = new int[maxIndex];for (int i = 0; i < maxIndex; i++) {leftNums[i] = nums[i];}int[] rightNums = new int[nums.length - maxIndex - 1];for (int i = maxIndex + 1; i < nums.length; i++) {rightNums[i - maxIndex - 1] = nums[i];}TreeNode node = new TreeNode(max, constructMaximumBinaryTree(leftNums), constructMaximumBinaryTree(rightNums));return node;}
}

看完代码随想录之后的想法 

        思路跟随想录第二个方法是一致的,第一个方法略有点复杂,还需要多加一次判断和取值,先pass。

        写法上我还有待改进,因为不想写多余的递归函数,所以就直接使用该函数为递归体了,但是也造成每次调用的时候,都要new两个新的数组,效率会降低(Java不像C++可以直接传地址)。像答案里面调用的递归函数入参写成原数组和头尾index就比较方便。此外,只有一个元素时,可以提前判断返回,这样也不需要额外再求一次最大值和构建左右子树的数组了。

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return constructMaximumBinaryTree1(nums, 0, nums.length);}public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) {if (rightIndex - leftIndex < 1) {// 没有元素了return null;}if (rightIndex - leftIndex == 1) {// 只有一个元素return new TreeNode(nums[leftIndex]);}int maxIndex = leftIndex;// 最大值所在位置int maxVal = nums[maxIndex];// 最大值for (int i = leftIndex + 1; i < rightIndex; i++) {if (nums[i] > maxVal){maxVal = nums[i];maxIndex = i;}}TreeNode root = new TreeNode(maxVal);// 根据maxIndex划分左右子树root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);return root;}
}

遇到的困难

        写起来不难,细节优化有待提升。

617.合并二叉树

题目链接:617.合并二叉树

代码随想录题解:617.合并二叉树

视频讲解:一起操作两个二叉树?有点懵!| LeetCode:617.合并二叉树_哔哩哔哩_bilibili

解题思路:

        操作两个树和操作一个树的方法其实差不多,递归每次同时传入位置相同的结点就行。因此递归的入参为两个树相同位置的子树根结点,返回值为合并后的根节点,终止条件是两个结点都为空。递归体为,如果两个结点都为空,不做操作直接返回null;如果其中一个结点为空,直接返回非空结点;如果都不为空,则new一个新的结点,其值为两个结点值之和,左子树和右子树都分别调用当前函数,入参分别为两个结点的左子树和右子树,最后返回该新结点。

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if (root1 == null && root2 == null) return null;else if (root1 != null && root2 == null) {return root1;} else if (root1 == null && root2 != null) {return root2;} else {return new TreeNode(root1.val + root2.val,mergeTrees(root1.left, root2.left),mergeTrees(root1.right, root2.right));}}
}

看完代码随想录之后的想法 

        递归法思路一致,迭代法也比较好理解,有符合条件的左右子树才加入队列,否则直接赋值,避免了队列中的元素有重复或者缺漏。不过写起来有些麻烦,就看看吧。

class Solution {
public:TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {if (t1 == NULL) return t2;if (t2 == NULL) return t1;queue<TreeNode*> que;que.push(t1);que.push(t2);while(!que.empty()) {TreeNode* node1 = que.front(); que.pop();TreeNode* node2 = que.front(); que.pop();// 此时两个节点一定不为空,val相加node1->val += node2->val;// 如果两棵树左节点都不为空,加入队列if (node1->left != NULL && node2->left != NULL) {que.push(node1->left);que.push(node2->left);}// 如果两棵树右节点都不为空,加入队列if (node1->right != NULL && node2->right != NULL) {que.push(node1->right);que.push(node2->right);}// 当t1的左节点 为空 t2左节点不为空,就赋值过去if (node1->left == NULL && node2->left != NULL) {node1->left = node2->left;}// 当t1的右节点 为空 t2右节点不为空,就赋值过去if (node1->right == NULL && node2->right != NULL) {node1->right = node2->right;}}return t1;}
};

遇到的困难

        无

700.二叉搜索树中的搜索

题目链接:​​​​​​​700.二叉搜索树中的搜索

代码随想录题解:700.二叉搜索树中的搜索

视频讲解:不愧是搜索树,这次搜索有方向了!| LeetCode:700.二叉搜索树中的搜索_哔哩哔哩_bilibili

解题思路:

        二叉搜索树本身就是通过一定的排序构造的,所以搜索效率极高。一般二叉搜索树的左子树所有结点比根结点小,右子树的所有结点比根结点大,所以搜索的时候只要通过递归或者迭代的方式,每层比较一次,就可以快速找到结果了。

递归法:入参为当前根结点和待搜索的值,返回值是布尔值,表示搜到与否,终止条件是搜到结果或当前结点为空(即不存在符合条件的值)。递归体为,如果当前结点的值等于目标值,直接返回true,如果当前结点值小于目标值,继续搜索该结点右子树,否则搜索该结点左子树。

class Solution {public TreeNode searchBST(TreeNode root, int val) {// 递归if (root == null || root.val == val) return root;if (val < root.val) return searchBST(root.left, val);else return searchBST(root.right, val);}
}

迭代法:按层序遍历的思路,用队列保存符合要求的结点,如果队首结点的值等于目标值,直接返回true,如果队首结点值小于目标值,将其右结点加入队列,否则将其左结点加入队列,直到队列为空返回false。

class Solution {public TreeNode searchBST(TreeNode root, int val) {// 迭代队列版if (root == null || root.val == val) return root;Queue<TreeNode> q = new LinkedList<>();q.add(root);while (!q.isEmpty()) {TreeNode node = q.poll();if (val == node.val) return node;if (val < node.val && node.left != null) q.add(node.left);if (val > node.val && node.right != null) q.add(node.right);}return null;}
}

看完代码随想录之后的想法 

        递归法是一样的,但是迭代法写复杂了,事实上都不需要队列或者栈去存数字,只要像链表那样一层一层直接往下搜索就好,非常简单。

class Solution {public TreeNode searchBST(TreeNode root, int val) {// 迭代极简版if (root == null || root.val == val) return root;if (val < root.val) root = root.left;else root = root.right;return searchBST(root, val);}
}

遇到的困难

        基础题,不难写

98.验证二叉搜索树

题目链接:98.验证二叉搜索树

代码随想录题解:98.验证二叉搜索树

视频讲解:你对二叉搜索树了解的还不够! | LeetCode:98.验证二叉搜索树_哔哩哔哩_bilibili

解题思路:

        一开始想用递归完成,利用二叉搜索树的性质,比较每个树根节点的值和其左右结点的值,如果左结点小于根结点,右结点大于根结点,该节点就符合要求,继续递归的判断左右子树是否符合要求即可。

        但是这样做会出错,原因是二叉搜索树要求的是左子树的每一个结点都小于根结点,右子树的每一个结点都大于根结点,只满足一层是不够的。然后看了一下leetcode上给的题解,用了一个新的递归函数,入参是当前节点和历史最大值及最小值,返回值是布尔值,表示树是否是二叉搜索树,终止条件为当前结点为空或者其值比历史最小值小或比历史最大值大。递归体为将当前节点的左右子树根结点分别放入递归函数,放左子树时,其输入的历史最大值为当前根结点的值,放右子树时,其输入的历史最小值为当前根结点的值。        

class Solution {TreeNode pre;public boolean isValidBST(TreeNode root) {if (root == null) return true;return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);}public boolean isValidBST(TreeNode root, long min, long max) {if (root == null) return true;if (root.val <= min || root.val >= max) return false;return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);}
}

看完代码随想录之后的想法 

        代码随想录给出的前序遍历得到数组判断该数组是否是递增数组的思路很清晰,虽然多了空间复杂度,但是很好理解。

// 简洁实现·中序遍历
class Solution {private long prev = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if (root == null) {return true;}if (!isValidBST(root.left)) {return false;}if (root.val <= prev) { // 不满足二叉搜索树条件return false;}prev = root.val;return isValidBST(root.right);}
}

        另一种递归只记录了用最大值去判断是否符合要求,着实是有点看不懂了,还是跳过吧。

遇到的困难

        第一次写完上传的时候就调入了陷阱,二叉搜索树的定义没有理解透彻,碰到不符合要求的树就出错了。参考答案写出含上下限的递归函数后,又因为测试用例里面包含了Integer的最大值和最小值,与初始化的值相同了,所以再次出错,仔细看了答案以后发现用的是long而非int变量,这样就不会有边界问题。也是蛮tricky的。

今日收获

        再次加深了一下二叉树的印象,学习二叉搜索树的定义和用法。递归函数的选择真的很奇妙,好好学习。

这篇关于代码随想录算法训练营第二十天| 654.最大二叉树,617.合并二叉树,700.二叉搜索树中的搜索,98.验证二叉搜索树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

闲置电脑也能活出第二春?鲁大师AiNAS让你动动手指就能轻松部署

对于大多数人而言,在这个“数据爆炸”的时代或多或少都遇到过存储告急的情况,这使得“存储焦虑”不再是个别现象,而将会是随着软件的不断臃肿而越来越普遍的情况。从不少手机厂商都开始将存储上限提升至1TB可以见得,我们似乎正处在互联网信息飞速增长的阶段,对于存储的需求也将会不断扩大。对于苹果用户而言,这一问题愈发严峻,毕竟512GB和1TB版本的iPhone可不是人人都消费得起的,因此成熟的外置存储方案开

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

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

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “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)的解 这个

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

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

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

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

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