代码随想录算法训练营第23期day19| 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

news/2025/3/16 11:44:23/

目录

一、(leetcode 654)最大二叉树

二、(leetcode 617)合并二叉树

三、(leetcode 700)二叉搜索树中的搜索

四、(leetcode 98)验证二叉搜索树


一、(leetcode 654)最大二叉树

力扣题目地址

状态:AC。

和昨天的中序+后/前序遍历序列构建二叉树思路类似,每次递归寻找数组中的最大值,根据最大值的索引来切分左右子序列进行递归生成,可以用索引下标来避免重复生成vector带来的开销

class Solution {
public:TreeNode* traversal(vector<int>& nums, int begin, int end){if(begin == end) { return nullptr; }int max_num = INT_MIN, max_index = begin;// 确定最大值的索引for(int i = begin; i < end; ++i){if(max_num < nums[i]){max_num = nums[i];max_index = i;}}TreeNode* node = new TreeNode(max_num);// 进行左右子数组划分int left_left = begin, left_right = max_index;int right_left = max_index + 1, right_right = end;node->left = traversal(nums, left_left, left_right);node->right = traversal(nums, right_left, right_right);return node;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {return traversal(nums, 0, nums.size());}
};

二、(leetcode 617)合并二叉树

力扣题目链接

状态:AC。

使用的方法可以AC但是不够简洁,留待后续改进

class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {//进行前序遍历,如果两棵树都为空则返回空节点if(root1 == nullptr && root2 == nullptr){return nullptr;}TreeNode* node = new TreeNode(0);if(root1 != nullptr && root2 != nullptr){node->val = root1->val + root2->val;node->left = mergeTrees(root1->left, root2->left);node->right = mergeTrees(root1->right, root2->right);}else if(root1){node->val = root1->val;node->left = mergeTrees(root1->left, nullptr);node->right = mergeTrees(root1->right, nullptr);}else{node->val = root2->val;node->left = mergeTrees(nullptr, root2->left);node->right = mergeTrees(nullptr, root2->right);}return node;  }
};

三、(leetcode 700)二叉搜索树中的搜索

力扣题目地址

状态:AC。

简单的前序遍历比较

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(root == nullptr) return nullptr;//前序遍历if(root->val == val){return root;}else if(root->val < val){return searchBST(root->right, val);}else{return searchBST(root->left, val);}return nullptr;}
};

四、(leetcode 98)验证二叉搜索树

力扣题目链接

状态:思路错误,不能简单地比较根节点和左右子节点的大小。

这道题可以通过中序遍历的顺序判断值是不是递增来判断,注意除了上面的那个思路问题,在实现时用于比较的值maxVal需要使用long long来初始化,以防测试用例中有INT_MIN。

class Solution {
public:long long maxVal = LONG_MIN;bool isValidBST(TreeNode* root) {if(root == nullptr) return true;bool left = isValidBST(root->left);//中序遍历查看是否符合递增if(root->val > maxVal){maxVal = root->val;}else{return false;}bool right = isValidBST(root->right);return left && right;}
};


http://www.ppmy.cn/news/1147528.html

相关文章

React 组件传 children 的各种方案

自定义组件的时候往往需要传 children&#xff0c;由于写法比较多样&#xff0c;我就总结了一下。 方案列表 1. 类组件1.1 类组件&#xff0c;不使用解构1.2 类组件&#xff0c;使用解构 2. 函数组件2.1 函数组件&#xff0c;不使用解构2.2 函数组件&#xff0c;外部解构2.3 函…

前端预览、下载二进制文件流(png、pdf)

前端请求设置 responseType: “blob” 后台接口返回的文件流如下&#xff1a; 拿到后端返回的文件流后&#xff1a; 预览 <iframe :src"previewUrl" frameborder"0" style"width: 500px; height: 500px;"></iframe>1、预览 v…

vue项目的学习周报03

学习周报 日期范围&#xff1a;2023年9月25日~2023年10月1日 学习目标&#xff1a;本周的学习目标是学习vue的基础知识 学习成果&#xff1a;在本周我完成以下任务和学习活动&#xff1a; 1.我完成了对vue.js的基础认识&#xff1b; 2.学习了通过index.js导入新的组件&#…

api接口为什么需要加密,PHP接口加密的方法有哪些

为什么需要进行加密: 保护敏感数据&#xff1a;许多应用程序需要在不同系统之间传输敏感数据&#xff0c;例如用户凭据、个人信息、金融信息等。接口加密可以确保这些敏感数据在传输过程中不会被未经授权的访问者窃取。 防止中间人攻击&#xff1a;在数据通过互联网传输的过程…

ubuntu安装Miniconda并举例使用

更新系统包 sudo apt update sudo apt upgrade官网下载Miniconda&#xff0c;最好是实体机下载后放进虚拟机&#xff0c;方法可以参考Xftp 7连接服务器或者本地虚拟机文章 https://docs.conda.io/en/latest/miniconda.html#linux-installers 进入安装目录执行&#xff0c;右键…

Python 集合(Sets)1

集合 集合用于在单个变量中存储多个项。集合是 Python 中的 4 种内置数据类型之一&#xff0c;用于存储数据集合&#xff0c;其他 3 种是列表&#xff08;List&#xff09;、元组&#xff08;Tuple&#xff09;和字典&#xff08;Dictionary&#xff09;&#xff0c;它们都具有…

ubuntu2204配置仓库为阿里源

官网上支持到2004&#xff0c;2204需要手动更改一下 deb https://mirrors.aliyun.com/ubuntu/ jammy main restricted universe multiverse deb-src https://mirrors.aliyun.com/ubuntu/ jammy main restricted universe multiversedeb https://mirrors.aliyun.com/ubuntu/ jam…

C# Onnx GFPGAN GPEN-BFR 人像修复

效果 项目 代码 using Microsoft.ML.OnnxRuntime; using Microsoft.ML.OnnxRuntime.Tensors; using OpenCvSharp; using System; using System.Collections.Generic; using System.Drawing; using System.Windows.Forms;namespace 图像修复 {public partial class Form1 : For…