算法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

相关文章

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

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

openCV中KNN算法的实现

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

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

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://