【数据结构与算法】:二叉树经典OJ
目录
- 1. 二叉树的前序遍历 (中,后序类似)
- 2. 二叉树的最大深度
- 3. 平衡二叉树
- 4. 二叉树遍历
1. 二叉树的前序遍历 (中,后序类似)
这道题的意思是对二叉树进行前序遍历,把每个结点的值都存入一个数组中,并且返回这个数组。
思路:
这题与我们平时写的二叉树前序遍历不同。需要我们自己开辟空间,但又由于二叉树结点个数未知,所以在开辟空间之前要先计算结点个数,根据结点个数开辟空间。最后再利用分治递归进行前序遍历。
代码实现如下:
注意:
(1) 结点个数的计算,数组空间的开辟;
(2) 递归时一般用子函数 _prevOrder 递归,而不是 preorderTraversal 原函数,不然会重复的开辟空间;
(3) 局部变量 i 一定要传地址,因为每一层递归函数都有一个 i ,下一层放的 i 是 i++之后的 i ,由于形参是实参的一份临时拷贝,若不传地址,就不会影响上一层函数中的 i ,就是加的不是同一个 i ;
(4) 输出型参数 returnSize ,目的是获取a数组有多大。
//前序遍历
void _prevOrder(struct TreeNode* root, int* a, int* pi)
{if (root == NULL)return;a[*pi] = root->val;(*pi)++;_prevOrder(root->left, a, pi);_prevOrder(root->right, a, pi);
}//由于不知道数组开多大的空间,所以要提前计算树的结点个数
int TreeSize(struct TreeNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}int* preorderTraversal(struct TreeNode* root, int* returnSize) {int size = TreeSize(root);//开辟数组空间int* a = (int*)malloc(sizeof(int) * size);int i = 0;_prevOrder(root, a, &i);*returnSize = size;return a;
}
2. 二叉树的最大深度
思路:
利用分治递归思想。若根节点为空,则深度为0;若非空,则先求左右子树的深度,我的深度 = 左右子树深度大的 + 1。
代码实现如下:
注意:
要先用两个变量记录计算好的左右子树的深度!不然运行时会超出时间限制。
int maxDepth(struct TreeNode* root) {if (root == NULL){return 0;}int leftDepth = maxDepth(root->left);int rightDepth = maxDepth(root->right);return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
3. 平衡二叉树
平衡二叉树:是指该树所有节点的左右子树的深度相差不超过 1。
思路:
首先计算出每个节点的左右子树的深度,再计算它们的深度差是否超过1。
代码实现如下:
int maxDepth(struct TreeNode* root) {if (root == NULL){return 0;}int leftDepth = maxDepth(root->left);int rightDepth = maxDepth(root->right);return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}bool isBalanced(struct TreeNode* root) {if (root == NULL)return true;int leftDepth = maxDepth(root->left);int rightDepth = maxDepth(root->right);//先检查自己满不满足,再递归检查左子树,右子树满不满足return abs(leftDepth - rightDepth) < 2&& isBalanced(root->left)&& isBalanced(root->right);
}
4. 二叉树遍历
思路:
首先要根据输入的字符串构建一棵二叉树,再进行中序遍历。
代码实现如下:
注意:
局部变量 i 要传地址,不然递归调用时加的不是同一个 i。
//定义结点
typedef struct TreeNode
{struct TreeNode* left;struct TreeNode* right;char val;
}TNode;//创建二叉树
TNode* CreateTree(char* a, int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}TNode* root = (TNode*)malloc(sizeof(TNode));if (root == NULL){perror("malloc fail!\n");exit(-1);}root->val = a[*pi];(*pi)++;root->left = CreateTree(a, pi);root->right = CreateTree(a, pi);return root;
}void InOrder(TNode* root)
{if (root == NULL)return;InOrder(root->left);printf("%c ", root->val);InOrder(root->right);
}int main() {char str[100] = { 0 };scanf("%s", str);int i = 0;//构建一棵树TNode* root = CreateTree(str, &i);InOrder(root);return 0;
}
相关文章:

【数据结构与算法】:二叉树经典OJ
目录 1. 二叉树的前序遍历 (中,后序类似)2. 二叉树的最大深度3. 平衡二叉树4. 二叉树遍历 1. 二叉树的前序遍历 (中,后序类似) 这道题的意思是对二叉树进行前序遍历,把每个结点的值都存入一个数组中,并且返回这个数组。 思路&…...

uniapp——长按识别二维码
说明 转变思路,长按图片,进入预览图片,这时候再长按就可以了。 <view class"codeMain"><view class"codeWhite" longpress"handleLongPress(i.image(qrcode))"><image :src"i.image(qrc…...

云服务器环境web环境搭建之JDK、redis、mysql
一、Linux安装jdk,手动配置环境 链接: https://pan.baidu.com/s/1LRgRC5ih7B9fkc588uEQ1whttps://pan.baidu.com/s/1LRgRC5ih7B9fkc588uEQ1w 提取码: 0413 tar -xvf 压缩包名 修改配置文件/etc/profile 二、安装redis环境 方案一: Linux下安装配置r…...

第1章 计算机网络体系结构
王道学习 【考纲内容】 (一)计算机网络概述 计算机网络的概念、组成与功能;计算机网络的分类; 计算机网络的性能指标 (二)计算机网络体系结构与参考模型 计算机网络分层结…...

Docker之自定义镜像上传至阿里云
一、Alpine介绍 Alpine Linux是一个轻量级的Linux发行版,专注于安全、简单和高效。它采用了一个小巧的内核和基于musl libc的C库,使得它具有出色的性能和资源利用率。 Alpine Linux的主要特点包括: 小巧轻量:Alpine Linux的安装…...

《深入Linux内核架构》第2章 进程管理和调度 (2)
目录 2.4 进程管理相关的系统调用 2.4.1 进程复制 2.4.2 内核线程 2.4.3 启动新程序 2.4.4 退出进程 本专栏文章将有70篇左右,欢迎关注,订阅后续文章。 2.4 进程管理相关的系统调用 2.4.1 进程复制 1. _do_fork函数 fork vfork clone都最终调用_…...

(四)PostgreSQL的psql命令
PostgreSQL的psql命令 基础信息 OS版本:Red Hat Enterprise Linux Server release 7.9 (Maipo) DB版本:16.2 pg软件目录:/home/pg16/soft pg数据目录:/home/pg16/data 端口:5777psql 是 PostgreSQL 数据库的命令行界面…...

前端使用minio传输文件
minio官方文档 minio-js可以支持ts。 安装完可能会出现 Can‘t import the named export ‘xxx‘ from non EcmaScript module (only default export is available)可以尝试降低minio的版本 npm install minio7.0.18 --save代码: 初始化 const Minio require(…...

[大模型] BlueLM-7B-Chat WebDemo 部署
BlueLM-7B-Chat WebDemo 部署 模型介绍 BlueLM-7B 是由 vivo AI 全球研究院自主研发的大规模预训练语言模型,参数规模为 70 亿。BlueLM-7B 在 C-Eval 和 CMMLU 上均取得领先结果,对比同尺寸开源模型中具有较强的竞争力(截止11月1号)。本次发布共包含 7…...

一文了解ERC404协议
一、ERC404基础讲解 1、什么是ERC404协议 ERC404协议是一种实验性的、混合的ERC20/ERC721实现的,具有原生流动性和碎片化的协议。即该协议可让NFT像代币一样进行拆分交易。是一个图币的互换协议。具有原生流动性和碎片化的协议。 这意味着通过 ERC404 协议…...

iOS cocoapods pod FrozenError and RuntimeError
0x00 报错日志 /Library/Ruby/Gems/2.6.0/gems/cocoapods-1.12.0/lib/cocoapods/user_interface/error_report.rb:34:in force_encoding: cant modify frozen String (FrozenError)from /Library/Ruby/Gems/2.6.0/gems/cocoapods-1.12.0/lib/cocoapods/user_interface/error_r…...

【鸿蒙开发】第二十章 Camera相机服务
1 简介 开发者通过调用Camera Kit(相机服务)提供的接口可以开发相机应用,应用通过访问和操作相机硬件,实现基础操作,如预览、拍照和录像;还可以通过接口组合完成更多操作,如控制闪光灯和曝光时间、对焦或调焦等。 2 …...

JS阅读笔记
myweb3.html <video id"video" width"400" height"300" autoplay></video> <button id"capture-btn">拍摄图片</button> <canvas id"canvas" width"400" height"300">&…...

基于spring boot的留守儿童爱心管理系统
基于spring boot的留守儿童爱心管理系统设计与实现 开发语言:Java 框架:springboot JDK版本:JDK1.8 服务器:tomcat7 数据库:mysql 5.7(一定要5.7版本) 数据库工具:Navicat11 开…...

python输入某年某月某日判断这一天是这一年的第几天
如何使用python实现输入某年某月某日判断这一天是这一年的第几天 from datetime import datetime #引入日期类 def is_leap_year(year):"""判断是否为闰年"""return (year % 4 0 and year % 100 ! 0) or (year % 400 0)# 根据年份和月份返回当…...

docker 上达梦导入dump文件报错:本地编码:PG GBK,导入女件编码:PGGB18030
解决方案: 第一步进入达梦数据容器内部 docker exec -it fc316f88caff /bin/bash 第二步:在容器中 /opt/dmdbms/bin目录下 执行命令 cd /opt/dmdbms/bin./dimp USERIDSYSDBA/SYSDBA001 FILE/opt/dmdbms/ZFJG_LJ20240407.dmp SCHEMASZFJG_LJUSERIDSYSD…...

一起学习python——基础篇(19)
今天来说一下python的如何修改文件名称、获取文件大小、读取文中指定的某一行内容。 1、修改文件名称: import os testPath"D:/pythonFile/test.txt" testPath2"D:/pythonFile/test2.txt" #修改文件名称使用rename方法, #第一个参…...

数模 初见数建
文章目录 初见数学建模1.1 数学建模是什么1.2 数学建模的概述1.3 如何学习数学建模---分模块化1.4 数学建模前提了解1.5 数学建模的六个步骤1.6 如何备战建模比赛1.7 数学建模赛题类型1.8 数学建模算法体系概述 初见数学建模 1.1 数学建模是什么 1.原型与模型 原型ÿ…...

windows系统搭建OCR半自动标注工具PaddleOCR
深度学习 文章目录 深度学习前言一、环境搭建准备方式1:安装Anaconda搭建1. Anaconda下载地址: [点击](https://mirrors.tuna.tsinghua.edu.cn/anaconda/archive/?CM&OD)2. 创建新的conda环境 方式2. 直接安装python 二、安装CPU版本1. 安装PaddlePaddle2、安装…...

01、ArcGIS For JavaScript 4.29对3DTiles数据的支持
综述 Cesium从1.99版本开始支持I3S服务的加载,到目前位置,已经支持I3S的倾斜模型、3D Object模型以及属性查询的支持。Cesium1.115又对I3S标准的Building数据实现了加载支持。而ArcGIS之前一直没有跨越对3DTiles数据的支持,所以在一些开发过…...

Spark_SparkSql写入Oracle_Undefined function.....将长字符串写入Oracle中方法..
在使用Spark编写代码将读库处理然后写入Oracle中遇到了诸多小bug,很磨人,好在解决了。shit!! 实测1:TO_CLOB(a3) 代码样例 --这是一个sparksql写入hive的一个小逻辑,我脱敏了噻 SELECT a1, a2, TO_CLOB(a3) AS clob_data, TO_DATE(a4) AS …...

2023数据要素白皮书(免费下载)
【1】关注本公众号,转发当前文章到微信朋友圈 【2】私信发送 【2023年数据资源入表白皮书】 【3】获取本方案PDF下载链接,直接下载即可。 如需下载本方案PPT原格式,请加入微信扫描以下方案驿站知识星球,获取上万份PPT解决方案&a…...

kafka学习记录
文章目录 windows单机版kafka搭建步骤主题的增删改查操作消息的生产与消费 Windows集群版kafka搭建步骤 prettyZoo 尚硅谷Kafka教程,2024新版kafka视频,零基础入门到实战 【尚硅谷】Kafka3.x教程(从入门到调优,深入全面࿰…...

无线网络2.4和5G的区别
无线网络2.4和5的区别 无线网络2.4GHz和5GHz的主要区别在于频率、覆盖范围、传输速度、干扰能力和穿透性。以下是详细介绍:12 频率不同。2.4GHz的频率较低,而5GHz的频率较高。频率越低,信号在传播过程中的损失越小,因此覆盖范围…...

大模型笔记:Prompt tuning
1 NLP模型的几个阶段 1.1 第一阶段(在深度学习出现之前) 通常聚焦于特征工程(feature engineering)利用领域知识从数据中提取好的特征 1.2 第二阶段(在深度学习出现之后) 特征可以从数据中习得——>…...

【Ambari】Ansible自动化部署大数据集群
目录 一.版本说明和介绍信息 1.1 大数据组件版本 1.2 Apache Components 1.3 Databases支持版本 二.安装包上传和说明 三.服务器基础环境配置 3.1global配置修改 3.2主机名映射配置 3.3免密用户名密码配置 3.4 ansible安装 四. 安…...

RTSP/Onvif视频安防监控平台EasyNVR调用接口返回匿名用户名和密码的原因排查
视频安防监控平台EasyNVR可支持设备通过RTSP/Onvif协议接入,并能对接入的视频流进行处理与多端分发,包括RTSP、RTMP、HTTP-FLV、WS-FLV、HLS、WebRTC等多种格式。平台拓展性强、支持二次开发与集成,可应用在景区、校园、水利、社区、工地等场…...

opencv基础图行展示
"""试用opencv创建画布并显示矩形框(适用于目标检测图像可视化) """ # 创建一个黑色的画布,图像格式(BGR) img np.zeros((512, 512, 3), np.uint8)# 画一个矩形:给定左上角和右下角坐标࿰…...

GIF在线生成器
上传图片就能生成GIF的前端WEB工具 源码也非常简单 <!DOCTYPE html> <html lang"zh" class"dark"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1, m…...

使用JavaScript制作一个简单的天气应用
随着Web开发技术的不断发展,JavaScript已经成为前端开发中不可或缺的一部分。它不仅可以用于创建动态和交互式的用户界面,还可以用于处理各种复杂的任务,如数据验证、动态内容更新、实时通信等。以下是一个使用JavaScript来创建一个简单天气应…...