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

相关文章

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Linux内核参数配置与验证详细指南

《Linux内核参数配置与验证详细指南》在Linux系统运维和性能优化中,内核参数(sysctl)的配置至关重要,本文主要来聊聊如何配置与验证这些Linux内核参数,希望对大家有一定的帮助... 目录1. 引言2. 内核参数的作用3. 如何设置内核参数3.1 临时设置(重启失效)3.2 永久设置(重启仍生效

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景:会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作?今天我要分享的Pyth... 目录一、项目概述:不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

jupyter代码块没有运行图标的解决方案

《jupyter代码块没有运行图标的解决方案》:本文主要介绍jupyter代码块没有运行图标的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录jupyter代码块没有运行图标的解决1.找到Jupyter notebook的系统配置文件2.这时候一般会搜索到