代码随想录算法训练营第二十天| 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

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调