算法day16|654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

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

算法day16|654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

  • 654.最大二叉树
  • 617.合并二叉树
    • 1.额外申请空间(失败)
    • 2.不额外申请空间
  • 700.二叉搜索树中的搜索
  • 98.验证二叉搜索树
    • 1.遍历后排序
    • 2.边遍历遍排序
    • 3.指针记录法

654.最大二叉树

这道题很简单,其实就是105、106的变式题。具体代码如下:

class Solution {
public:TreeNode*traversal(vector<int>& nums){if(nums.empty())return nullptr;int max=nums[0];int index=0;for(int i=1;i<nums.size();i++){if(nums[i]>max){max=nums[i];index=i;} }TreeNode*root=new TreeNode(max);if(nums.size()==1)return root;vector<int> leftNums(nums.begin(),nums.begin()+index);vector<int> rightNums(nums.begin()+index+1,nums.end());root->left=traversal(leftNums);root->right=traversal(rightNums);return root;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {if(!nums.empty())return traversal(nums);elsereturn nullptr;}
};

总体思路与105、106类似,甚至更简单。

617.合并二叉树

1.额外申请空间(失败)

不知道为什么运行不了…,代码如下:

class Solution {
public:TreeNode* traversal(TreeNode* root1, TreeNode* root2){if(root1==nullptr&&root2==nullptr)return nullptr;TreeNode*root=new TreeNode();if(root1!=nullptr&&root2!=nullptr)root->val=root1->val+root2->val;else if(root1==nullptr&&root2!=nullptr)root->val=root2->val;else if(root1!=nullptr&&root2==nullptr)root->val=root1->val;root->left=traversal(root1->left,root2->left);root->right=traversal(root1->right,root2->right);return root;}TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {return traversal(root1,root2);}
};

2.不额外申请空间

class Solution {
public:
TreeNode* traversal(TreeNode* root1, TreeNode* root2){if(!root1&&!root2)return nullptr;else if(!root1)return root2;else if(!root2)return root1;else{root1->val+=root2->val;}root1->left=traversal(root1->left,root2->left);root1->right=traversal(root1->right,root2->right);return root1;}TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {return traversal(root1,root2);}
};

直接在root1上进行操作,不用额外申请空间。

700.二叉搜索树中的搜索

class Solution {
public:TreeNode* traversal(TreeNode* root, int val){if(root==nullptr)return nullptr;if(root->val>val)return traversal(root->left,val);if(root->val<val)return traversal(root->right,val);elsereturn root;}TreeNode* searchBST(TreeNode* root, int val) {return traversal(root,val);}
};

要注意一下BST的特点:BST首先得是二叉平衡树,满足左<中<右。所以:

if(root->val>val)return traversal(root->left,val);if(root->val<val)return traversal(root->right,val);

另外,如果递归有返回值的话,在单层递归里面肯定是需要设置变量来接收的,或者直接return 递归。

98.验证二叉搜索树

1.遍历后排序

class Solution {
public:void traversal(TreeNode* root,vector<int> &vec){if(root==nullptr)return ;traversal(root->left,vec);vec.push_back(root->val);traversal(root->right,vec);}bool isValidBST(TreeNode* root) {if(root==nullptr)return true;else{vector<int> vec;traversal(root,vec);for(int i=0;i<vec.size()-1;i++){if(vec[i]>=vec[i+1])return false;}return true;}}
};

这题的易错点就是必须保证左子树上的所有元素都要小于根节点,右子树同理,而不是仅仅是单个左孩子结点或者右孩子结点。这样的思路用递归就很难实现了。

所以我们另辟蹊径,利用二叉搜索树的最重要的特征之一:中序序列单调递增 。我们只需要用数组收集中序序列,然后去判断它是否递增即可。

2.边遍历遍排序

对于递增的判断其实是可以在遍历过程中就实现的,代码如下:

class Solution {
public:long long MaxValue = LONG_MIN;bool traversal(TreeNode* root){if(root==nullptr)return true;bool left=traversal(root->left);if(root->val>MaxValue)MaxValue=root->val;elsereturn false; bool right=traversal(root->right);return left&&right;}bool isValidBST(TreeNode* root) {return traversal(root);}
};

为了判断中序序列是否递增,我们需要一个值来继承之前结点的大小,然后与当前结点比较即可。由于力扣中输入了Int的最小值,所以我们采用long long型的最小值来接受第一个元素,十分巧妙:

		long long MaxValue = LONG_MIN;if(root->val>MaxValue)MaxValue=root->val;elsereturn false;

这样就可以保证第一个数的顺利进行。因为不想for循环,递归的时候是很难定位到第几个元素的,所以想把第哪个元素赋值为几,这是做不到的。只有在深刻理解逻辑之后做一些巧思。

3.指针记录法

class Solution {
public:TreeNode*pre=nullptr;bool traversal(TreeNode* root){if(root==nullptr)return true;bool left=traversal(root->left);if(pre!=nullptr&&pre->val>=root->val)return false;elsepre=root;bool right=traversal(root->right);return left&&right;}bool isValidBST(TreeNode* root) {return traversal(root);}
};

我们改用指针来记录,实现一个更巧妙的逻辑:用指针记录前面的值,只有当指针的值大于当前的值时,return false。问题在于,指针该如何记录呢?逻辑很巧妙,因为记录第一个值是非常关键的。初始时,我们设pre为null,第一次就是因为pre为null,成功赋值;其他时候是因为满足排序,所以成功赋值。它们的逻辑是有区别的。

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



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

相关文章

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.图