算法打卡day17|二叉树篇06|Leetcode 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

本文主要是介绍算法打卡day17|二叉树篇06|Leetcode 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

算法题

Leetcode  654.最大二叉树

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

大佬视频讲解:最大二叉树视频讲解

个人思路

大概思路就是在数组中 找最大值的节点作为当前节点,用最大值的index切割左右子树的区间,往复循环到数组元素为0;

解法

递归法

按照思路来看递归法是不错的选择;可以采用前序遍历,因为是先构造中间节点,然后递归构造左子树和右子树

 1.确定递归函数的参数和返回值参数

传入的是存放元素的数组返回该数组构造的二叉树的头结点,返回类型是指向节点的指针。

2.确定终止条件

题目中说了输入的数组大小一定是大于等于1的,所以不用考虑小于1的情况,那么当递归遍历的时候,如果传入的数组大小为1,说明遍历到了叶子节点了。

那么应该定义一个新的节点,并把这个数组的数值赋给新的节点,然后返回这个节点。 这表示一个数组大小是1的时候,构造了一个新的节点,并返回。

 3.确定单层递归的逻辑

 1.先要找到数组中最大的值和对应的下标最大的值构造根节点,下标用来下一步分割数组

 2.最大值所在的下标左区间 构造左子树

这里要判断maxValueIndex > 0,因为要保证左区间至少有一个数值

 3.最大值所在的下标右区间 构造右子树

判断maxValueIndex < (nums.size() - 1),确保右区间至少有一个数值

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;}
}

时间复杂度:O(n);(遍历整棵树,每个元素最多被访问一次)

空间复杂度:O(n);(递归树的高度h)


Leetcode 617.合并二叉树

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

大佬视频讲解:合并二叉树视频讲解

个人思路

这个和构造一颗二叉树差不多,只是需要同时操控两棵树,所以只用同时遍历两棵二叉树,把树A和树B的节点值相加到树A,最后返回树A即可;

解法
递归法

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if (root1 == null) return root2;//2.确定终止条件if (root2 == null) return root1;//3.确定单层递归的逻辑root1.val += root2.val;//两颗数节点值相加root1.left = mergeTrees(root1.left,root2.left);//左树合并root1.right = mergeTrees(root1.right,root2.right);//右树合并return root1;//1.确定递归函数的参数和返回类型}
}

时间复杂度:O(n);(最差遍历一遍树)

空间复杂度:O(n);(递归树的高度h)

迭代法

也可以用队列,模拟的层序遍历,同时遍历,将值加到一棵树上,最后返回这棵树;

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if (root1 == null) return root2;if (root2 ==null) return root1;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root1);queue.offer(root2);while (!queue.isEmpty()) {TreeNode node1 = queue.poll();TreeNode node2 = queue.poll();// 此时两个节点一定不为空,val相加node1.val = node1.val + node2.val;// 如果两棵树左节点都不为空,加入队列if (node1.left != null && node2.left != null) {queue.offer(node1.left);queue.offer(node2.left);}// 如果两棵树右节点都不为空,加入队列if (node1.right != null && node2.right != null) {queue.offer(node1.right);queue.offer(node2.right);}// 若node1的左节点为空,直接赋值if (node1.left == null && node2.left != null) {node1.left = node2.left;}// 若node1的右节点为空,直接赋值if (node1.right == null && node2.right != null) {node1.right = node2.right;}}return root1;}
}

时间复杂度:O(n);(遍历2棵树)

空间复杂度:O(n);(使用两个队列)


Leetcode 700.二叉搜索树中的搜索

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

 大佬视频讲解:二叉搜索树中的搜索视频讲解

个人思路

对于普通二叉树和搜素树都能递归法,一层层找,找到节点值与目标值相同时,返回该节点。

解法

回顾一下二叉搜索树,它是一个有序树:

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  • 它的左、右子树也分别为二叉搜索树

递归法

可以根据二叉搜索树的特性(left<root, right>root),优化一下递归

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);//往右搜索}}
}

递归搜索普通二叉树的代码如下:

class Solution {// 递归,普通二叉树public TreeNode searchBST(TreeNode root, int val) {if (root == null || root.val == val) {return root;}TreeNode left = searchBST(root.left, val);if (left != null) {return left;}return searchBST(root.right, val);}
}

时间复杂度:O(n);(最差遍历一遍树)

空间复杂度:O(n);(递归树的高度h)

迭代法

因为二叉搜索树的特殊性,也就是节点的有序性,可以不使用辅助栈或者队列就可以写出迭代法。

对于一般二叉树,递归过程中还有回溯的过程,例如走一个左方向的分支走到头了,那么要调头,在走右分支。而对于二叉搜索树,不需要回溯的过程,因为节点的有序性就帮我们确定了搜索的方向。

例如要搜索元素为11的节点,不需要搜索其他节点,也不需要做回溯,查找的路径已经规划好了。中间节点如果大于11就向左走,如果小于11就向右走,如图:

class Solution {public TreeNode searchBST(TreeNode root, int val) {//不用栈也能模拟递归while (root != null)if (val < root.val) root = root.left;else if (val > root.val) root = root.right;else return root;return null;}
}

时间复杂度:O(n);(遍历整棵树)

空间复杂度:O(1);(没有使用其他辅助空间)

迭代搜索普通二叉树代码如下:

class Solution {// 迭代,普通二叉树public TreeNode searchBST(TreeNode root, int val) {if (root == null || root.val == val) {return root;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode pop = stack.pop();if (pop.val == val) {return pop;}if (pop.right != null) {stack.push(pop.right);}if (pop.left != null) {stack.push(pop.left);}}return null;}
}

时间复杂度:O(n);(遍历整棵树)

空间复杂度:O(n);(使用栈模拟递归)


Leetcode 98.验证二叉搜索树

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

大佬视频讲解:验证二叉搜索树视频讲解

个人思路

刚刚做完搜索树,但如何验证搜索树的思路却不清晰...

解法
递归法

首先这道题目比较容易犯个错误:

不能单纯的比较左节点小于中间节点,右节点大于中间节点

因为搜索树要比较的是 左子树所有节点小于中间节点,右子树所有节点大于中间节点

例如: [10,5,15,null,null,6,20] 这个case:

节点10大于左节点5,小于右节点15,但右子树里出现了一个6 这就不符合了!

然后继续递归三步走,这里采用中序遍历,因为要先知道根节点的值,再去比较左右子节点:

1.确定递归函数,返回值以及参数

如果没有找到这个节点就遍历了整个树,如果找到不符合的节点了,立刻返回。

2.确定终止条件

如果是空节点 也是二叉搜索树

3.确定单层递归的逻辑

中序遍历,一直更新maxVal,一旦发现maxVal >= root->val,就返回false,注意元素相同时候也要返回false。

class Solution {TreeNode max;public boolean isValidBST(TreeNode root) {if (root == null) {return true;}// 左boolean left = isValidBST(root.left);if (!left) {return false;}// 中if (max != null && root.val <= max.val) {return false;}max = root;// 右boolean right = isValidBST(root.right);return right;}
}

时间复杂度:O(n);(遍历二叉树)

空间复杂度:O(n);(递归树的高度h)

迭代法

可以用栈模拟递归中序遍历;

class Solution {  public boolean isValidBST(TreeNode root) {if (root == null) {return true;}Stack<TreeNode> stack = new Stack<>();TreeNode pre = null;while (root != null || !stack.isEmpty()) {while (root != null) {stack.push(root);root = root.left;// 左}// 中,处理节点,判断大小TreeNode pop = stack.pop();if (pre != null && pop.val <= pre.val) {return false;}pre = pop;root = pop.right;// 右}return true;}
}

时间复杂度:O(n);(遍历二叉树)

空间复杂度:O(n);(模拟递归的栈)


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

这篇关于算法打卡day17|二叉树篇06|Leetcode 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

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

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

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

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Python实现合并与拆分多个PDF文档中的指定页

《Python实现合并与拆分多个PDF文档中的指定页》这篇文章主要为大家详细介绍了如何使用Python实现将多个PDF文档中的指定页合并生成新的PDF以及拆分PDF,感兴趣的小伙伴可以参考一下... 安装所需要的库pip install PyPDF2 -i https://pypi.tuna.tsingh

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

使用Apache POI在Java中实现Excel单元格的合并

《使用ApachePOI在Java中实现Excel单元格的合并》在日常工作中,Excel是一个不可或缺的工具,尤其是在处理大量数据时,本文将介绍如何使用ApachePOI库在Java中实现Excel... 目录工具类介绍工具类代码调用示例依赖配置总结在日常工作中,Excel 是一个不可或缺的工http://

使用Python创建一个能够筛选文件的PDF合并工具

《使用Python创建一个能够筛选文件的PDF合并工具》这篇文章主要为大家详细介绍了如何使用Python创建一个能够筛选文件的PDF合并工具,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录背景主要功能全部代码代码解析1. 初始化 wx.Frame 窗口2. 创建工具栏3. 创建布局和界面控件4

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

Python爬虫selenium验证之中文识别点选+图片验证码案例(最新推荐)

《Python爬虫selenium验证之中文识别点选+图片验证码案例(最新推荐)》本文介绍了如何使用Python和Selenium结合ddddocr库实现图片验证码的识别和点击功能,感兴趣的朋友一起看... 目录1.获取图片2.目标识别3.背景坐标识别3.1 ddddocr3.2 打码平台4.坐标点击5.图