【代码随想录】【算法训练营】【第20天】 [654]最大二叉树 [617]合并二叉树 [700]二叉搜索树中的搜索 [98]验证二叉搜索树

前言

思路及算法思维,指路 代码随想录。
题目来自 LeetCode。

day 19,一个愉快的周日~
day 20,一个悲伤的周一~

题目详情

[654] 最大二叉树

题目描述

654 最大二叉树
654 最大二叉树

解题思路

前提:构造二叉树
思路:寻找根节点,左子树范围、右子树范围递归构造子树。
重点:注意数组的范围,左闭右开。

代码实现

C语言
虚拟头节点
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int maxFun(int *nums, int numsSize, int *max)
{
    int maxVal = INT_MIN;
    int loc = 0;
    for (int i = 0; i < numsSize; i++)
    {
        if (nums[i] > maxVal)
        {
            maxVal = nums[i];
            loc = i;
        }
    }
    *max = maxVal;
    return loc;
}

void addNode(struct TreeNode **root, int *nums, int numsSize)
{
    if (numsSize == 0)
    {
        return ;
    }
    // 寻找最大值做根节点
    int maxVal = 0;
    int maxLoc = maxFun(nums, numsSize, &maxVal);
    // 保存该值为根节点
    *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    (*root)->val = maxVal;
    (*root)->left = NULL;
    (*root)->right = NULL;
    // 构造左子树
    addNode(&((*root)->left), nums, maxLoc);
    // 构造右子树
    addNode(&((*root)->right), nums + maxLoc + 1, numsSize - maxLoc - 1);
    return ;
}

struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize) {
    if (numsSize == 0)
    {
        return NULL;
    }
    struct TreeNode *root = NULL;
    addNode(&root, nums, numsSize);
    return root;
}

[617] 合并二叉树

题目描述

617 合并二叉树
617 合并二叉树

解题思路

前提:合并二叉树
思路:二叉树位置重合时,结点值相加;位置仅有一个时,使用该结点,直接改变父节点的子节点的指针指向。
重点:注意结点不仅为非空的情况。

代码实现

C语言
先序遍历 递归
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

void traversal(struct TreeNode **root1, struct TreeNode *root2)
{
    // 结点判空
    if (*root1 == NULL)
    {
        *root1 = root2;
        return ;
    }
    if (root2 == NULL)
    {
        return ;
    }
    // 两节点均不为空
    (*root1)->val += root2->val;
    // 遍历左右子树
    traversal(&((*root1)->left), root2->left);
    traversal(&((*root1)->right), root2->right);
    return ;
}

struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2) {
    traversal(&root1, root2);
    return root1;
}
层级遍历 队列
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2) {
    // 判空
    if (root1 == NULL)
    {
        return root2;
    }
    if (root2 == NULL)
    {
        return root1;
    }
    // 层级遍历 队列
    struct TreeNode *queue[2000];
    int idx = 0;
    queue[idx++] = root1;
    queue[idx++] = root2;
    int start = 0;
    while (start < idx)
    {
        struct TreeNode *curNode1 = queue[start++];
        struct TreeNode *curNode2 = queue[start++];
        curNode1->val += curNode2->val;
        // 判断左子树情况
        if ((curNode1->left == NULL) && (curNode2->left != NULL))
        {
            curNode1->left = curNode2->left;
        }
        else if ((curNode1->left != NULL) && (curNode2->left != NULL))
        {
            queue[idx++] = curNode1->left;
            queue[idx++] = curNode2->left;
        }
        // 判断右子树情况
        if ((curNode1->right == NULL) && (curNode2->right != NULL))
        {
            curNode1->right = curNode2->right;
        }
        else if ((curNode1->right != NULL) && (curNode2->right != NULL))
        {
            queue[idx++] = curNode1->right;
            queue[idx++] = curNode2->right;
        }
    }
    return root1;
}

[700] 二叉搜索树中的搜索

题目描述

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

解题思路

前提:二叉搜索树的搜索
思路:二叉搜索树的结点是有序的,先序序列数组是递增的。
重点:二叉搜索树的特点。

代码实现

C语言
先序遍历 递归
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* searchBST(struct TreeNode* root, int val) {
    if (root == NULL)
    {
        return NULL;
    }
    if (root->val == val)
    {
        return root;
    }
    // 遍历左右子树
    struct TreeNode *ans = searchBST(root->left, val);
    if (ans == NULL)
    {
        ans = searchBST(root->right, val);
    }
    return ans;
}
先序递归,平衡二叉树结点有序特性
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* searchBST(struct TreeNode* root, int val) {
    if ((root == NULL) || (root->val == val))
    {
        return root;
    }
    if (root->val > val)
    {
        // 遍历左子树
        return searchBST(root->left, val);
    }
    else
    {
        // 遍历右子树
        return searchBST(root->right, val);
    }
}

[98] 验证二叉搜索树

题目描述

98 验证二叉搜索树
98 验证二叉搜索树

解题思路

前提:判断是否为二叉搜索树
思路:根据二叉搜索树的定义,可以递归判断该二叉树是否为二叉搜索树,可以中序遍历该树,看是否为递增数组。
重点:该树为二叉搜索树要求不仅仅是根节点值大于左子结点值、小于右子结点值,而是根节点大于左子树的最底层最右结点值、小于右子树的最底层最左结点值。

代码实现

C语言
中序遍历,遍历后判断递增
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

void traversal(struct TreeNode *root, int *nums, int *numsSize)
{
    if (root == NULL)
    {
        return ;
    }
    // 中序遍历
    // 左
    traversal(root->left, nums, numsSize);
    // 中
    nums[(*numsSize)++] = root->val;
    // 右
    traversal(root->right, nums, numsSize);
    return ;
}

bool isValidBST(struct TreeNode* root) {
    int nums[10000];
    int numsSize = 0;
    traversal(root, nums, &numsSize);
    for (int i = 1; i < numsSize; i++)
    {
        if (nums[i] <= nums[i - 1])
        {
            return false;
        }
    }
    return true;
}
中序遍历,遍历时判断递增

保存当前遍历的节点的最大值,中序遍历中需要不断判断大于该值。
注意:不能使用全局变量,用例测试时不会重置全局变量。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isValidBSTFun(struct TreeNode* root, long long *maxVal)
{
    // 判断空节点或者单节点
    if (root == NULL)
    {
        return true;
    }
    // 左子树 小于
    bool ansLeft = isValidBSTFun(root->left, maxVal);
    // 中
    if (root->val <= *maxVal)
    {
        return false;
    }
    else
    {
        *maxVal = root->val;
    }
    // 右子树 大于
    bool ansRight = isValidBSTFun(root->right, maxVal);
    return ((ansLeft) && (ansRight));
}

bool isValidBST(struct TreeNode* root) {
    long long maxVal = LONG_MIN;
    return isValidBSTFun(root, &maxVal);
}

今日收获

  1. 二叉树构造;
  2. 二叉搜索树的特征。

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

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

相关文章

基于Django框架的项目搭建后台首页

(1). 创建数据库 osdb 进入MySQL数据库中&#xff0c;创建一个数据库名为&#xff1a;osdb 通过数据表结构来创建数据表&#xff1a; -- 员工信息表 CREATE TABLE user (id int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT 员工账号id,username varchar(50) DEFAULT NULL C…

路径规划 | 图解粒子群(PSO)算法(附ROS C++仿真)

目录 0 专栏介绍1 从鸟群迁徙说起2 粒子群算法基本概念3 粒子群算法流程4 粒子群算法ROS实现 0 专栏介绍 &#x1f525;附C/Python/Matlab全套代码&#x1f525;课程设计、毕业设计、创新竞赛必备&#xff01;详细介绍全局规划(图搜索、采样法、智能算法等)&#xff1b;局部规…

跨境热销爆款货源哪里找?选品工具不能少

通常&#xff0c;跨境电商找热销货源的几种方法&#xff1a; 1、使用Google Trends、亚马逊销售排行等来追踪和分析当前的市场趋势和热门产品&#xff1b; 2、关注社交媒体、行业论坛和博客等渠道&#xff0c;以获取最新的市场信息和消费者反馈&#xff1b; 3、在主流的跨境…

Oracle实践|内置函数之数学型函数

&#x1f4eb; 作者简介&#xff1a;「六月暴雪飞梨花」&#xff0c;专注于研究Java&#xff0c;就职于科技型公司后端工程师 &#x1f3c6; 近期荣誉&#xff1a;华为云云享专家、阿里云专家博主、腾讯云优秀创作者、ACDU成员 &#x1f525; 三连支持&#xff1a;欢迎 ❤️关注…

CDC 数据实时同步入湖的技术、架构和方案(截至2024年5月的现状调研)

近期&#xff0c;对 “实时摄取 CDC 数据同步到数据湖” 这一技术主题作了一系列深入的研究和验证&#xff0c;目前这部分工作已经告一段落&#xff0c;本文把截止目前&#xff08;2024年5月&#xff09;的研究结果和重要结论做一下梳理和汇总。为了能给出针对性的技术方案&…

基于小波分析和机器学习(SVM,KNN,NB,MLP)的癫痫脑电图检测(MATLAB环境)

癫痫是一种由大脑神经元突发性异常放电导致的大脑功能性障碍疾病。据世界卫生组织统计&#xff0c;全球约有7000万人患有癫痫。癫痫患者在发病时呈现肌肉抽搐、呼吸困难、意识丧失等症状。由于癫痫发作的偶然性&#xff0c;患者极有可能在高空、驾驶、游泳等危险情况下发病并丧…

掌握栈回溯意味着什么?

来源&#xff1a;公众号【鱼鹰谈单片机】 作者&#xff1a;鱼鹰Osprey ID &#xff1a;emOsprey 历时两个月&#xff08;1/3&#xff09;&#xff0c;第一个完成电子表项目的学员出现了&#xff0c;并且顺利的掌握了栈回溯技巧&#xff0c;在工作中快速定位了一个任务异常挂起…

【STM32】 独立看门狗配置方法

什么是看门狗 看门狗&#xff08;watchdog&#xff09;指的是一种监控系统或程序&#xff0c;用于定期检测和监控其他系统或程序的运行状态&#xff0c;并在出现问题或故障时采取相应的措施。它可以是硬件设备&#xff0c;也可以是软件程序。 在计算机领域中&#xff0c;看门狗…

全国青少年信息素养大赛历届复赛、国赛真题

由于2024年信息素养大赛初赛比较简单&#xff0c;特别是Scrath图形化编程和Python编程&#xff0c;八九分钟及半个小时内交卷的也多&#xff0c;100分及80分以上的比较多&#xff0c;&#xff08;各赛区复赛晋级根据两个指标进行排名&#xff0c;初赛成绩和答题用时。首先根据分…

AC/DC电源模块:提供高质量的电力转换解决方案

BOSHIDA AC/DC电源模块&#xff1a;提供高质量的电力转换解决方案 AC/DC电源模块是一种电力转换器件&#xff0c;可以将交流电转换为直流电。它通常用于各种电子设备和系统中&#xff0c;提供高质量的电力转换解决方案。 AC/DC电源模块具有许多优点。首先&#xff0c;它能够提…

玩机进阶教程------固件中的分区表 gpt_backup0.bin gpt_both0.bin gpt_main0.bin有什么区别 怎么修改分区表【一】

不管是emmc还是ufs在官方的线刷包中都有分区表存在。分区表包含有各个分区的地址段落。如果你在fast模式刷入官方固件还解决不了系统问题。那有几率是分区表损坏。这种情况无论你怎么刷写分区是解决不了问题的。 此类话题在百度很难搜索到,大多都是讲分区表的类型 结构 等等,…

23种设计模式全面总结 | 快速复习(附PDF+MD版本)

本篇文章是对于23种设计模式的一个全面的总结&#xff0c;受限于文章篇幅无法对每个设计模式做到全面的解析&#xff0c;但几乎每个设计模式都提供了案例和类图结构&#xff0c;非常适合快速复习和在学习设计模式之前的全预习把握。 &#x1f4a1;文章的 pdf markdown 版本可通…

驱动开发执行应用层时报ELF: not found,syntax error: unexpected “(“错误

问题&#xff1a; 原因&#xff1a;在跨平台的时候注意我们使用的编译器&#xff0c;我是因为没有没有交叉编译导致的。 出问题之前使用的是gcc test_01_normal.c -o test_01_normal生成的文件&#xff0c;导致&#xff0c;执行时报ELF这种问题。 解决办法&#xff1a;arm-li…

将本地项目上传到 gitee 仓库

1、创建 gitee 仓库 到 gitee 官网&#xff0c;新建仓库 配置新建仓库 完成仓库的创建 项目上传到仓库 上传项目需要安装git git官方下载地址&#xff1a;git下载地址 安装完成&#xff0c;前往本地项目所在文件夹&#xff0c;右击选择 Git Bash Here 刚下载完成需要配置G…

粤嵌—2024/5/13—删除排序链表中的重复元素(✔)

代码实现&#xff1a; /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/ struct ListNode* deleteDuplicates(struct ListNode *head) {if (head NULL || head->next NULL) {return head;}struct ListNode *…

【计算机毕业设计】基于SSM+Vue的新能源汽车在线租赁管理系统【源码+lw+部署文档】

摘 要 随着科学技术的飞速发展&#xff0c;社会的方方面面、各行各业都在努力与现代的先进技术接轨&#xff0c;通过科技手段来提高自身的优势&#xff0c;新能源汽车在线租赁当然也不能排除在外。新能源汽车在线租赁是以实际运用为开发背景&#xff0c;运用软件工程开发方法&…

【Linux部署】【pig前端部署】Linux安装- docker/docker-compose/nginx (使用docker优雅部署nginx)

&#x1f338;&#x1f338; Linux安装- docker/docker-compose/nginx 优雅部署 &#x1f338;&#x1f338; 一、一键安装jdk yum install -y java-1.8.0-openjdk.x86_64验证 二、安装docker yum list docker-ce --showduplicates | sort -rsudo yum install -y yum-utils …

Visual Studio和Visual Studio Code分清了? 都是IDE,可不是框架。

Visual Studio和VSCode两者都是 Microsoft 制造的IDE&#xff08;集成开发环境&#xff09;。尽管它们的名字相似&#xff0c;但它们的功能却大不相同。 一、什么是Visual Studio&#xff08;VS&#xff09; Visual Studio&#xff08;简称VS&#xff09;是由微软公司开发的一…

用go语言实现一个有界协程池

写在文章开头 本篇文章算是对go语言系列的一个收尾&#xff0c;通过go语言实现一个实现一个简单的有界协程池。 Hi&#xff0c;我是 sharkChili &#xff0c;是个不断在硬核技术上作死的 java coder &#xff0c;是 CSDN的博客专家 &#xff0c;也是开源项目 Java Guide 的维护…

AIGC时代算法工程师的面试秘籍(2024.4.29-5.12第十三式) |【三年面试五年模拟】

写在前面 【三年面试五年模拟】旨在整理&挖掘AI算法工程师在实习/校招/社招时所需的干货知识点与面试方法&#xff0c;力求让读者在获得心仪offer的同时&#xff0c;增强技术基本面。也欢迎大家提出宝贵的优化建议&#xff0c;一起交流学习&#x1f4aa; 欢迎大家关注Rocky…