Day17.一刷数据结构算法(C语言版) 654最大二叉树；617合并二叉树；700二叉搜索树中的搜索；98验证二叉搜索树

2024-04-23 09:44
文章标签 算法 二叉树 数据结构 搜索 验证 最大 二叉 一刷 树中 98 合并 语言版 700 day17 654 617

本文主要是介绍Day17.一刷数据结构算法(C语言版) 654最大二叉树；617合并二叉树；700二叉搜索树中的搜索；98验证二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

        又是破防的一天......

一.654最大二叉树

        又是构造二叉树，昨天大家刚刚做完 中序后序确定二叉树，今天做这个 应该会容易一些， 先看视频，好好体会一下 为什么构造二叉树都是 前序遍历 

        题目链接：最大二叉树

        文章讲解：代码随想录

        视频讲解：又是构造二叉树，又有很多坑！| LeetCode：654.最大二叉树

 1.思路分析

        简单来说，二叉树构建过程如下：

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

        递归三部曲：

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

        参数传入的是存放元素的数组以及左右边界索引，返回该数组构造的二叉树的头结点，返回类型是指向节点的指针。

struct TreeNode* traversal(int* nums, int left, int right)

         2）确定终止条件

        当左右边界相等或左右颠倒时，返回NULL。

//若左边界大于右边界，返回NULLif(left >= right)return NULL;

        3）确定单层递归的逻辑

        第一步：先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组。

//找出数组中最大数坐标int maxIndex = left;int i;for(i = left + 1; i < right; i++) {if(nums[i] > nums[maxIndex])maxIndex = i;}//开辟结点struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));//将结点的值设为最大数组数组元素node->val = nums[maxIndex];

        第二步：最大值所在的下标左区间构造左子树。

node->left = traversal(nums, left, maxIndex);

        第三步：最大值所在的下标右区间构造右子树。

node->right = traversal(nums, maxIndex + 1, right);

2.代码详解

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
struct TreeNode* traversal(int* nums, int left, int right) {//若左边界大于右边界，返回NULLif(left >= right)return NULL;//找出数组中最大数坐标int maxIndex = left;int i;for(i = left + 1; i < right; i++) {if(nums[i] > nums[maxIndex])maxIndex = i;}//开辟结点struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));//将结点的值设为最大数组数组元素node->val = nums[maxIndex];//递归定义左孩子结点和右孩子结点node->left = traversal(nums, left, maxIndex);node->right = traversal(nums, maxIndex + 1, right);return node;
}struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize){return traversal(nums, 0, numsSize);
}

 二.617合并二叉树

        这次是一起操作两个二叉树了， 估计大家也没一起操作过两个二叉树，也不知道该如何一起操作，可以看视频先理解一下。 优先掌握递归。

        题目链接：合并二叉树

        文章讲解：代码随想录

        视频讲解：一起操作两个二叉树？有点懵！| LeetCode：617.合并二叉树_哔哩哔哩_bilibili

 1.思路分析

        其实和遍历一个树逻辑是一样的，只不过传入两个树的节点，同时操作。

        这道题用哪种遍历都可以，本人以前序为例。

        递归三部曲：

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

        首先要合入两个二叉树，那么参数至少是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点。 

struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2)

        2）确定终止条件

        因为是传入了两个树，那么就有两个树遍历的节点root1 和 root2，如果root1 == NULL 了，两个树合并就应该是 root2 了（如果root2也为NULL也无所谓，合并之后就是NULL）。

        反过来如果root2 == NULL，那么两个数合并就是root1（如果root1也为NULL也无所谓，合并之后就是NULL）。

        代码如下：

if (root1 == NULL) return root2; // 如果root1为空，合并之后就应该是root2
if (root2 == NULL) return root1; // 如果root2为空，合并之后就应该是root1

         3）确定单层递归的逻辑

        单层递归的逻辑就比较好写了，这里我们重复利用一下root1这个树，root1就是合并之后树的根节点（就是修改了原来树的结构）。

        那么单层递归中，就要把两棵树的元素加到一起。

root->val=root1->val+root2->val;

        接下来root1 的左子树是：合并root1左子树root2左子树之后的左子树。

        root1 的右子树：是 合并 root1右子树 root2右子树之后的右子树。

        最终t1就是合并之后的根节点。

root->left=mergeTrees(root1->left,root2->left);
root->right=mergeTrees(root1->right,root2->right);
return root;

 2.代码详解

/*** 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* root=(struct TreeNode*)malloc(sizeof(struct TreeNode));root->val=root1->val+root2->val;root->left=mergeTrees(root1->left,root2->left);root->right=mergeTrees(root1->right,root2->right);return root;
}

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

        递归和迭代 都可以掌握以下，因为本题比较简单， 了解一下 二叉搜索树的特性

        题目链接：二叉搜索树中的搜索

        文章讲解: 代码随想录

        视频讲解：不愧是搜索树，这次搜索有方向了！| LeetCode：700.二叉搜索树中的搜索

1.思路分析

        本题，其实就是在二叉搜索树中搜索一个节点。那么我们来看看应该如何遍历。

        递归三部曲：

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

        递归函数的参数传入的就是根节点和要搜索的数值，返回的就是以这个搜索数值所在的节点。

        代码如下：

struct TreeNode* searchBST(struct TreeNode* root, int val)

         2）确定终止条件

        如果root为空，或者找到这个数值了，就返回root节点。

if (root == NULL || root->val == val) return root;

        3） 确定单层递归的逻辑

        看看二叉搜索树的单层递归逻辑有何不同。

        因为二叉搜索树的节点是有序的，所以可以有方向的去搜索。

        如果root->val 大于val，搜索左子树，如果root->val 小于 val，就搜索右子树，最后如果都没有搜索到，就返回NULL。

struct TreeNode* result = NULL;
if (root->val > val) result = searchBST(root->left, val);
if (root->val < val) result = searchBST(root->right, val);
return result;

        很多人写递归函数的时候习惯直接写searchBST(root->right, val)，却忘了递归函数还有返回值。

        递归函数的返回值是什么? 是左子树如果搜索到了val，要将该节点返回。 如果不用一个变量将其接住，那么返回值不就没了。

        所以要result = searchBST(root->right, val);并在最后return result。

2.代码详解

/*** 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;struct TreeNode* result = NULL;if (root->val > val) result = searchBST(root->left, val);if (root->val < val) result = searchBST(root->right, val);return result;
}

 四.98验证二叉搜索树

        遇到 搜索树，一定想着中序遍历，这样才能利用上特性。 

        但本题是有陷阱的，可以自己先做一做，然后在看题解，看看自己是不是掉陷阱里了。这样理解的更深刻。

        题目链接：验证二叉搜索树

        文章讲解：代码随想录

        视频讲解：你对二叉搜索树了解的还不够！ | LeetCode：98.验证二叉搜索树

 1.思路分析

        要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。

        有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。

        这道题目比较容易陷入两个陷阱：

  • 陷阱1

        不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。

        我们要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点。

        例如： [10,5,15,null,null,6,20] 这个case：

 

        节点10大于左节点5，小于右节点15，但右子树里出现了一个6 这就不符合了！ 

  • 陷阱2

        样例中最小节点可能是int的最小值，如果这样使用最小的int来比较也是不行的。

        此时可以初始化比较元素为longlong的最小值。

        （不过本人写的代码并没有考虑longlong的情况，所以如果你比较顾虑，可以自行修改）

        递归三部曲：

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

bool isValid(struct TreeNode* root,struct TreeNode** pre)

（悄悄话：其中，pre为用来记录前一个节点的指针的指针，我一开始本想当作全局变量放在函数前面。测试的时候没问题，但是提交的时候，面对{0}的输入，输出错误，也不知道怎么回事。如果你平时有认真看我的博客的话，你会发现我上一次也用了指针的指针来代替全局变量，错误的具体原因我也不太清楚，这也是我今天破防的原因。我回头再研究一下。我破防的另一个原因是，在第三题，我遍历的时候脑袋短路了，当时就是不明白为什么在最后要写返回值......）

        2）确定终止条件

        如果是空节点 是不是二叉搜索树呢？

        是的，二叉搜索树也可以为空！

if (root == NULL) return true;

        3）确定单层递归的逻辑

bool left = isValid(root->left,pre);if (*pre != NULL && (*pre)->val >= root->val) return false;
*pre = root; // 记录前一个节点bool right = isValid(root->right,pre);
return left && right;

2.代码详解

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
bool isValid(struct TreeNode* root,struct TreeNode** pre) {if (root == NULL) return true;bool left = isValid(root->left,pre);if (*pre != NULL && (*pre)->val >= root->val) return false;*pre = root; // 记录前一个节点bool right = isValid(root->right,pre);return left && right;
}
bool isValidBST(struct TreeNode* root){struct TreeNode* pre = NULL;return isValid(root,&pre);
}

         如果你有问题或者有其他想法，欢迎评论区留言，大家可以一起探讨。

 

 

 

 

 

 

 

 

这篇关于Day17.一刷数据结构算法(C语言版) 654最大二叉树；617合并二叉树；700二叉搜索树中的搜索；98验证二叉搜索树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/928448。

相关文章

代码随想录算法训练营：12/60

代码随想录算法训练营：12/60

非科班学习算法day12 | LeetCode150:逆波兰表达式 ，Leetcode239: 滑动窗口最大值  目录 介绍 一、基础概念补充： 1.c++字符串转为数字 1. std::stoi, std::stol, std::stoll, std::stoul, std::stoull（最常用） 2. std::stringstream 3. std::atoi, std
阅读更多...
android 免费短信验证功能

android 免费短信验证功能

没有太复杂的使用的话，功能实现比较简单粗暴。 在www.mob.com网站中可以申请使用免费短信验证功能。 步骤： 1.注册登录。 2.选择“短信验证码SDK” 3.下载对应的sdk包，我这是选studio的。 4.从头像那进入后台并创建短信验证应用，获取到key跟secret 5.根据技术文档操作（initSDK方法写在setContentView上面） 6.关键：在有用到的Mo
阅读更多...
人工智能机器学习算法总结神经网络算法(前向及反向传播)

人工智能机器学习算法总结神经网络算法(前向及反向传播)

1.定义，意义和优缺点 定义: 神经网络算法是一种模仿人类大脑神经元之间连接方式的机器学习算法。通过多层神经元的组合和激活函数的非线性转换，神经网络能够学习数据的特征和模式，实现对复杂数据的建模和预测。(我们可以借助人类的神经元模型来更好的帮助我们理解该算法的本质，不过这里需要说明的是，虽然名字是神经网络，并且结构等等也是借鉴了神经网络，但其原型以及算法本质上还和生物层面的神经网络运行原理存在
阅读更多...
20170723 做的事 ecdsa的签名验证时间短于bls signature

20170723 做的事 ecdsa的签名验证时间短于bls signature

1 今天在虚拟机 /home/smile/Desktop/20170610/Test//time_ecdsa 文件夹下，找到ecdsa的验证时间是 989.060606μs μs 先 make ，然后run。 再取BLS的签名生成时间： ./run  2  gnuplot 画图，画对比的时间 gnuplot 画图参考教程 http://blog.sciencen
阅读更多...
【数据结构】线性表：顺序表

【数据结构】线性表：顺序表

文章目录 1. 线性表2. 顺序表2.1 概念及结构2.2 接口实现2.3 顺序表的问题及思考 1. 线性表 线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式
阅读更多...
DDS信号的发生器（验证篇）——FPGA学习笔记8

DDS信号的发生器（验证篇）——FPGA学习笔记8

前言：第一部分详细讲解DDS核心框图，还请读者深入阅读第一部分，以便理解DDS核心思想 三刷小梅哥视频总结！ 小梅哥https://www.corecourse.com/lander 一、DDS简介         DDS（Direct Digital Synthesizer）即数字合成器，是一种新型的频率合成技术，具有低成本、低功耗、高分辨率、频率转换时间短、相位连续性好等优点，对数字信
阅读更多...
数据结构9——排序

数据结构9——排序

一、冒泡排序 冒泡排序（Bubble Sort），顾名思义，就是指越小的元素会经由交换慢慢“浮”到数列的顶端。 算法原理 从左到右，依次比较相邻的元素大小，更大的元素交换到右边；从第一组相邻元素比较到最后一组相邻元素，这一步结束最后一个元素必然是参与比较的元素中最大的元素；按照大的居右原则，重新从左到后比较，前一轮中得到的最后一个元素不参4与比较，得出新一轮的最大元素；按照上述规则，每一轮结
阅读更多...
大林 PID 算法

大林 PID 算法

Dahlin PID算法是一种用于控制和调节系统的比例积分延迟算法。以下是一个简单的C语言实现示例： #include <stdio.h>// DALIN PID 结构体定义typedef struct {float SetPoint; // 设定点float Proportion; // 比例float Integral; // 积分float Derivative; // 微分flo
阅读更多...
剑指offer（C++）--平衡二叉树

剑指offer（C++）--平衡二叉树

题目 输入一棵二叉树，判断该二叉树是否是平衡二叉树。 class Solution {public:bool IsBalanced_Solution(TreeNode* pRoot) {if(pRoot==NULL)return true;int left_depth = getdepth(pRoot->left);int right_depth = getdepth(pRoot->rig
阅读更多...
二叉树三种遍历方式及其实现

二叉树三种遍历方式及其实现

一、基本概念 每个结点最多有两棵子树，左子树和右子树，次序不可以颠倒。 性质： 1、非空二叉树的第n层上至多有2^(n-1)个元素。 2、深度为h的二叉树至多有2^h-1个结点。 3、对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。 满二叉树：所有终端都在同一层次，且非终端结点的度数为2。 在满二叉树中若其深度为h，则其所包含
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2