当前位置: 首页 > news >正文

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

uniapp——长按识别二维码

说明 转变思路&#xff0c;长按图片&#xff0c;进入预览图片&#xff0c;这时候再长按就可以了。 <view class"codeMain"><view class"codeWhite" longpress"handleLongPress(i.image(qrcode))"><image :src"i.image(qrc…...

云服务器环境web环境搭建之JDK、redis、mysql

一、Linux安装jdk&#xff0c;手动配置环境 链接: https://pan.baidu.com/s/1LRgRC5ih7B9fkc588uEQ1whttps://pan.baidu.com/s/1LRgRC5ih7B9fkc588uEQ1w 提取码: 0413 tar -xvf 压缩包名 修改配置文件/etc/profile 二、安装redis环境 方案一&#xff1a; Linux下安装配置r…...

第1章 计算机网络体系结构

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

Docker之自定义镜像上传至阿里云

一、Alpine介绍 Alpine Linux是一个轻量级的Linux发行版&#xff0c;专注于安全、简单和高效。它采用了一个小巧的内核和基于musl libc的C库&#xff0c;使得它具有出色的性能和资源利用率。 Alpine Linux的主要特点包括&#xff1a; 小巧轻量&#xff1a;Alpine Linux的安装…...

《深入Linux内核架构》第2章 进程管理和调度 (2)

目录 2.4 进程管理相关的系统调用 2.4.1 进程复制 2.4.2 内核线程 2.4.3 启动新程序 2.4.4 退出进程 本专栏文章将有70篇左右&#xff0c;欢迎关注&#xff0c;订阅后续文章。 2.4 进程管理相关的系统调用 2.4.1 进程复制 1. _do_fork函数 fork vfork clone都最终调用_…...

(四)PostgreSQL的psql命令

PostgreSQL的psql命令 基础信息 OS版本&#xff1a;Red Hat Enterprise Linux Server release 7.9 (Maipo) DB版本&#xff1a;16.2 pg软件目录&#xff1a;/home/pg16/soft pg数据目录&#xff1a;/home/pg16/data 端口&#xff1a;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代码&#xff1a; 初始化 const Minio require(…...

[大模型] BlueLM-7B-Chat WebDemo 部署

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

一文了解ERC404协议

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

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(相机服务)提供的接口可以开发相机应用&#xff0c;应用通过访问和操作相机硬件&#xff0c;实现基础操作&#xff0c;如预览、拍照和录像&#xff1b;还可以通过接口组合完成更多操作&#xff0c;如控制闪光灯和曝光时间、对焦或调焦等。 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的留守儿童爱心管理系统设计与实现 开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09; 数据库工具&#xff1a;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

解决方案&#xff1a; 第一步进入达梦数据容器内部 docker exec -it fc316f88caff /bin/bash 第二步&#xff1a;在容器中 /opt/dmdbms/bin目录下 执行命令 cd /opt/dmdbms/bin./dimp USERIDSYSDBA/SYSDBA001 FILE/opt/dmdbms/ZFJG_LJ20240407.dmp SCHEMASZFJG_LJUSERIDSYSD…...

一起学习python——基础篇(19)

今天来说一下python的如何修改文件名称、获取文件大小、读取文中指定的某一行内容。 1、修改文件名称&#xff1a; import os testPath"D:/pythonFile/test.txt" testPath2"D:/pythonFile/test2.txt" #修改文件名称使用rename方法&#xff0c; #第一个参…...

数模 初见数建

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

windows系统搭建OCR半自动标注工具PaddleOCR

深度学习 文章目录 深度学习前言一、环境搭建准备方式1&#xff1a;安装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服务的加载&#xff0c;到目前位置&#xff0c;已经支持I3S的倾斜模型、3D Object模型以及属性查询的支持。Cesium1.115又对I3S标准的Building数据实现了加载支持。而ArcGIS之前一直没有跨越对3DTiles数据的支持&#xff0c;所以在一些开发过…...

Spark_SparkSql写入Oracle_Undefined function.....将长字符串写入Oracle中方法..

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

2023数据要素白皮书(免费下载)

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

kafka学习记录

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

无线网络2.4和5G的区别

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

大模型笔记:Prompt tuning

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

【Ambari】Ansible自动化部署大数据集群

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

RTSP/Onvif视频安防监控平台EasyNVR调用接口返回匿名用户名和密码的原因排查

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

opencv基础图行展示

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

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