leetcode654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索

654.最大二叉树

构造树一般采用的是前序遍历,因为先构造中间节点,然后递归构造左子树和右子树

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

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

TreeNode* constructMaximumBinaryTree(vector<int>& nums)
  • 确定终止条件

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

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

TreeNode* node = new TreeNode(0);
if (nums.size() == 1) {
    node->val = nums[0];
    return node;
}
  • 确定单层递归的逻辑

这里有三步工作

  1. 先要找到数组中最大的值和对应的下标, 最大的值构造根节点,下标用来下一步分割数组
int maxValue = 0;
int maxValueIndex = 0;
for (int i = 0; i < nums.size(); i++) {
    if (nums[i] > maxValue) {
        maxValue = nums[i];
        maxValueIndex = i;
    }
}
TreeNode* node = new TreeNode(0);
node->val = maxValue;
  1. 最大值所在的下标左区间 构造左子树
    这里要判断maxValueIndex > 0,因为要保证左区间至少有一个数值
if (maxValueIndex > 0) {
    vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
    node->left = constructMaximumBinaryTree(newVec);
}
  1. 最大值所在的下标右区间 构造右子树
    判断maxValueIndex < (nums.size() - 1),确保右区间至少有一个数值
if (maxValueIndex < (nums.size() - 1)) {
    vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());
    node->right = constructMaximumBinaryTree(newVec);
}

这样我们就分析完了,整体代码如下:(详细注释)

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* node = new TreeNode(0);
        if(nums.size() == 1){
            node->val = nums[0];
            return node;
        } 
        // 找到数组中最大的值和对应的下标
        int maxValue = nums[0];
        int maxValueIndex = 0;
        for(int i = 0; i < nums.size(); i++){
            if(maxValue < nums[i]){
                maxValue = nums[i];
                maxValueIndex = i;
            }
        }

        node->val = maxValue;
        // 最大值所在的下标左区间 构造左子树
        if(maxValueIndex > 0){
            vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
            node->left = constructMaximumBinaryTree(newVec);
        }
        // 最大值所在的下标右区间 构造右子树
        if(maxValueIndex < nums.size() - 1){
            vector<int> newVec(nums.begin() + 1 + maxValueIndex, nums.end());
            node->right = constructMaximumBinaryTree(newVec);
        }
        
        return node;
    }

617.合并二叉树

使用队列,模拟的层序遍历,代码如下:

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1 == NULL) return root2;
        if(root2 == NULL) return root1;
        
        queue<TreeNode*> que;
        que.push(root1);
        que.push(root2);
        while(!que.empty()){
            TreeNode* node1 = que.front();
            que.pop();
            TreeNode* node2 = que.front();
            que.pop();
            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);
            }
            if(node1->left == NULL && node2->left != NULL){
                node1->left = node2->left;
            }
            if(node1->right == NULL && node2->right != NULL){
                node1->right =node2->right;
            }
        }
        return root1;
    }
};

700.二叉搜索树中的搜索

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        TreeNode* node = root;
        while(node != NULL ){
            if(node->val > val) {
                node = node->left;
            } else if (node->val < val) {
                node = node->right;
            } else{
                return node;
            }
        }
        return NULL;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/634960.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Redis的下载、安装、启动和初尝试【超级简单】

redis最好是在Linux系统中使用&#xff0c;这是最接近生产实际的环境。 不过&#xff0c;我们初学者&#xff0c;目的是学习Redis的使用、原理&#xff0c;如果在Linux下直接学习Redis&#xff0c;很可能会因为命令不熟悉而劝退&#xff0c;这是不好的。 因此&#xff0c;我主张…

国际货币基金组织警告:网络攻击影响全球金融稳定

近日&#xff0c;在一份关于金融稳定的报告中&#xff0c;国际货币基金组织&#xff08;IMF&#xff09;用了一章&#xff08;共三章&#xff09;的篇幅描述了网络攻击对金融环境的影响&#xff0c;并警告称&#xff0c;全球金融稳定正受到日益频繁和复杂的网络攻击的威胁。同时…

kubernetes(k8s) v1.30.1 创建本地镜像仓库 使用本地docker镜像仓库部署服务 Discuz X3.5 容器搭建论坛

1 master11创建本地镜像仓库 [rootmaster11 ~]# docker run -d -p 5000:5000 --restartalways --name registry registry:2 Unable to find image registry:2 locally 2: Pulling from library/registry 79e9f2f55bf5: Pull complete 0d96da54f60b: Pull complete 5b27040df…

是德科技 DSOS104A MSOS104A示波器

产品 带宽 通道数 最大存储器深度 DSOS104A 高清晰度示波器 1 GHz 4 个模拟通道 800 Mpts MSOS104A 高清晰度示波器 1 GHz 4 个模拟通道和 16 个数字通道 800 Mpts 商品介绍 …

ELK 日志监控平台(一)- 快速搭建

文章目录 ELK 日志监控平台&#xff08;一&#xff09;- 快速搭建1.ELK 简介2.Elasticsearch安装部署3.Logstash安装部署4.Kibana安装部署5.日志收集DEMO5.1.创建SpringBoot应用依赖导入日志配置文件 logback.xml启动类目录结构启动项目 5.2.创建Logstash配置文件5.3.重新启动L…

锁相环的一些学习笔记--(1)

下图两组1.2.3可以对应起来&#xff1b; 参考资料&#xff1a; 1. Matlab https://www.bilibili.com/video/BV1bR4y1Z7Xg/?spm_id_from333.1296.top_right_bar_window_history.content.click&vd_source5556680656536651c49f5e55d7d4df23 2. https://www.bilibili.com/…

Hadoop开发之JavaAPI操作HDFS

目录 一、maven的安装与配置1.maven的下载2.maven的安装与配置&#xff08;1&#xff09;解压&#xff08;2&#xff09;创建本地仓库文件夹&#xff08;3&#xff09;修改settings.xml配置文件&#xff08;4&#xff09;配置maven的环境变量&#xff08;5&#xff09;idea中ma…

将list对象里的某一个属性取出组成一个新的list

使用Java8将对象里的某一个属性取出组成一个新的list List<Spgg1> listnew ArrayList<>();Spgg1 spgg1new Spgg1();spgg1.setSpdm("测试");spgg1.setGgdm("001");list.add(spgg1);Spgg1 spgg2new Spgg1();spgg2.setSpdm("测试2");sp…

不用从头训练,通过知识融合创建强大的统一模型

在自然语言处理&#xff08;NLP&#xff09;领域&#xff0c;大型语言模型&#xff08;LLMs&#xff09;的开发和训练是一个复杂且成本高昂的过程。数据需求是一个主要问题&#xff0c;因为训练这些模型需要大量的标注数据来保证其准确性和泛化能力&#xff1b;计算资源也是一个…

基于 Prometheus 的超算弹性计算场景下主机监控最佳实践

作者&#xff1a;左知 超算场景的业务特点 主机监控&#xff0c;或许是监控/可观测领域最传统和普遍的需求。在超算训练&#xff0c;AI 大规模训练的业务场景下&#xff0c;主机监控又有哪些痛点和难点呢&#xff1f;根据我们针对多个大规模超算客户的需求整理&#xff0c;超…

LeetCode:柱状图中最大的矩形

文章收录于LeetCode专栏 LeetCode地址 柱状图中最大的矩形 题目 给定 n 个非负整数&#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻&#xff0c;且宽度为 1 。求在该柱状图中&#xff0c;能够勾勒出来的矩形的最大面积。 示例1 **输入&#xff1a;**heights …

FastAPI单元测试:使用TestClient轻松测试你的API

当使用FastAPI进行单元测试时&#xff0c;一个重要的工具是TestClient类。TestClient类允许我们模拟对FastAPI应用程序的HTTP请求&#xff0c;并测试应用程序的响应。这使我们能够在不启动服务器的情况下对API进行全面的测试。 下面我将详细讲解TestClient的使用方法和常见操作…

empirecms 文件上传 (CVE-2018-18086)

漏洞环境&#xff1a;vulfocus 到管理后台 使用用户名密码&#xff1a;admin:123456登录&#xff0c;然后到后台找到文件上传点 发现需要后缀名为.mod 创建生成一句话木马的php脚本&#xff0c;并添加.mod后缀名&#xff0c;然后提交 <?php file_put_contents("shell…

攻防世界---web---warmup

1、题目描述 2、查看源码&#xff0c;发现有个source.php 3、访问该文件&#xff0c;得到这一串代码 4、分析代码 5、访问hint.php&#xff0c;提示flag在ffffllllaaaagggg这个文件下 6、构造payload ?filesource.php?/../../../../../../ffffllllaaaagggg

网络性能与流量监控:优化企业网络管理的关键策略

目录 网络性能监控的重要性 1. 提高网络可靠性 2. 优化网络资源使用 3. 提升用户体验 网络流量监控的必要性 1. 识别异常流量 2. 改善网络管理 3. 确保合规性 AnaTraf网络流量分析仪&#xff1a;提升网络监控效率的利器 如何实施有效的网络监控策略 1. 确定监控目标…

php发送短信功能(创蓝短信)

一、以下是创蓝发送短信的功能&#xff0c;可以直接执行&#xff1a; <?php$phone 12312312312;$msg 测试短信功能;echo 发送手机号&#xff1a;.$phone.<br/>;echo 发送内容&#xff1a;.$msg.<br/>;$send sendMessage($phone, $msg);var_dump($send);…

2024电工杯数学建模 - 案例:最短时间生产计划安排

# 前言 2024电工杯(中国电机工程学会杯)数学建模思路解析 最新思路更新(看最新发布的文章即可): https://blog.csdn.net/dc_sinor/article/details/138726153 最短时间生产计划模型 该模型出现在好几个竞赛赛题上&#xff0c;预测2022今年国赛也会与该模型相关。 1 模型描…

BUUCTF---misc---我吃三明治

1、下载附件是一张图片 2、在winhex分析&#xff0c;看到一串整齐的编码有点可疑&#xff0c;保存下来&#xff0c;拿去解码&#xff0c;发现解不了&#xff0c;看来思路不对 3、再仔细往下看的时候也发现了一处这样的编码&#xff0c;但是这次编码后面多了一段base编码 4、拿去…

抖音小店什么产品最好卖?六月份的必爆产品!商家抓紧上架!

哈喽~我是电商月月 做抖音小店&#xff0c;爆款是非常吃香的&#xff0c;但普通玩家只有在爆款出来的那几天才能发现&#xff0c;再去截流&#xff0c;其实热度已经不高了&#xff0c;那想吃到这一口“螃蟹”只能自己去挖掘 每年爆的产品就是那几种&#xff0c;我们可以朝这几…

java自学阶段二:JavaWeb开发--day04(Maven学习)

day04学习笔记 一、学习目标 1.了解maven的基础概念&#xff1b; 2.学会maven的部署&#xff1b; 3.maven的作用&#xff1a;标准化&#xff1b;方便找依赖 maven就是一个开源项目&#xff0c;专门用来管理和构建Java项目的&#xff1b;我们自己写的项目结构可能会千奇百怪&am…
最新文章