[数据结构]二叉树OJ(leetcode)
目录
二叉树OJ(leetcode)训练习题::
1.单值二叉树
2.检查两棵树是否相同
3.二叉树的前序遍历
4.另一棵树的子树
5.二叉树的构建及遍历
6.二叉树的销毁
7.判断二叉树是否是完全二叉树
二叉树OJ(leetcode)训练习题::
1.单值二叉树

//单值二叉树
//思路:相等的传递性
struct TreeNode
{int val;struct TreeNode* left;struct TreeNode* right;
};
bool isUnivalTree(struct TreeNode* root)
{if (root == NULL)return true;if (root->left && root->val != root->left->val)return false;if (root->right && root->val != root->right->val)return false;//走到此位置说明当前的父亲和孩子是相等的return isUnivalTree(root->left) && isUnivalTree(root->right);
}
2.检查两棵树是否相同

//相同的树
//思路:根比较 子树比较
struct TreeNode
{int val;struct TreeNode* left;struct TreeNode* right;
};
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{if (p == NULL && q == NULL)return true;//其中一个为空 另一个不为空if (p == NULL || q == NULL)return false;//都不为空if (p->val != q->val)return false;//走到此位置说明p,q均不为空,且根的值是相等的return isSameTree(p->left, q->right) && isSameTree(p->right, q->right);
}
3.二叉树的前序遍历

//二叉树的前序遍历
//要求:既要返回数组的首地址 又要返回数组的长度
struct TreeNode
{int val;struct TreeNode* left;struct TreeNode* right;
};
int TreeSize(struct TreeNode* root)
{if (root == NULL)return 0;return TreeSize(root->left) + TreeSize(root->right) + 1;
}
void preorder(struct TreeNode* root, int* a, int* pi)
{if (root == NULL)return;a[*pi] = root->val;(*pi)++;preorder(root->left, a, pi);preorder(root->right, a, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{int n = TreeSize(root);int* a = (int*)malloc(sizeof(int) * n);int i = 0;preorder(root, a, &i);*returnSize = n;return a;
}
4.另一棵树的子树

//另一棵树的子树
//思路:原树中的每棵子树都和subRoot树比较+相同的树代码
struct TreeNode
{int val;struct TreeNode* left;struct TreeNode* right;
};
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{if (p == NULL && q == NULL)return true;//其中一个为空 另一个不为空if (p == NULL || q == NULL)return false;//都不为空if (p->val != q->val)return false;//走到此位置说明p,q均不为空,且根的值是相等的return isSameTree(p->left, q->right) && isSameTree(p->right, q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{if (root == NULL)return false;if (isSameTree(root, subRoot))return true;return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
5.二叉树的构建及遍历

//二叉树遍历
//通过前序遍历的数组构建二叉树
typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;
//递归的下一层++在返回时 不会影响上一层 所以要传地址
//注意:树的每个节点不是递归的时候链接上的 而是在返回的时候链接上的 root->left = BinaryTreeCreate(a,pi)
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc fail");return NULL;}root->data = a[*pi];(*pi)++;root->left = BinaryTreeCreate(a, pi);root->right = BinaryTreeCreate(a, pi);return root;
}
void InOrder(BTNode* root)
{if (root == NULL){return;}InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}
6.二叉树的销毁
//二叉树销毁
//外面调用该函数的人置空
void BinaryTreeDestory(BTNode* root)
{if (root == NULL){return;}BinaryTreeDestory(root->left);BinaryTreeDestory(root->right);free(root);
}
7.判断二叉树是否是完全二叉树
//判断二叉树是否是完全二叉树
//思路:层序遍历,一层一层走,遇到空以后,后续层序不能有非空,有非空就不是完全二叉树
//注:完全二叉树遇到空以后 后面节点一定都入队列了
//复制粘贴队列代码
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;
//第三种不用二级指针的方式 封装成结构体
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
//取队列头部数据
QDataType QueueFront(Queue* pq);
//取队列尾部数据
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
#include"Queue.h"
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}
void QueueDestory(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* del = cur;cur = cur->next;free(del);}pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}else{newnode->data = x;newnode->next = NULL;}if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* del = pq->head;pq->head = pq->head->next;free(del);del = NULL;}pq->size--;
}
//取队列头部数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}
//取队列尾部数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL && pq->tail == NULL;
}
int QueueSize(Queue* pq)
{assert(pq);/*QNode* cur = pq->head;int n = 0;while (cur){++n;cur = cur->next;}return n;*/return pq->size;
}
int BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL){break;}QueuePush(&q, front->left);QueuePush(&q, front->right);}//遇到空以后 后面全是空 则是完全二叉树//遇到空以后 后面存在非空 则不是完全二叉树while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front != NULL){QueueDestory(&q);return false;}}QueueDestory(&q);return true;
}
相关文章:
[数据结构]二叉树OJ(leetcode)
目录 二叉树OJ(leetcode)训练习题:: 1.单值二叉树 2.检查两棵树是否相同 3.二叉树的前序遍历 4.另一棵树的子树 5.二叉树的构建及遍历 6.二叉树的销毁 7.判断二叉树是否是完全二叉树 二叉树OJ(leetcode)训练习题:: 1.单值二叉…...
flutter 输入时插入分隔符
每四位插入一个分隔符import package:flutter/services.dart;class DividerInputFormatter extends TextInputFormatter {final int rear; //第一个分割位数,后面分割位,,数final String pattern; //分割符DividerInputFormatter({this.rear 4, this.pattern });overrideTex…...
静态版通讯录——“C”
各位CSDN的uu你们好呀,之前小雅兰学过了一些结构体、枚举、联合的知识,现在,小雅兰把这些知识实践一下,那么,就让我们进入通讯录的世界吧 实现一个通讯录: 可以存放100个人的信息每个人的信息:名…...
前端基础开发环境搭建工具等
一、基本开发环境(软件)安装1、Vscode(代码编辑器)官网下载网址:https://code.visualstudio.com/2、nvm(node多版本管理器,每个node版本都有对应的npm版本)安装包下载地址࿱…...
华为OD机试题【IPv4 地址转换成整数】用 Java 解 | 含解题说明
华为Od必看系列 华为OD机试 全流程解析+经验分享,题型分享,防作弊指南华为od机试,独家整理 已参加机试人员的实战技巧华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典本篇题目:IPv4 地址转换成整数 题目 存在…...
[数据结构]排序算法
目录 常用排序算法的实现:: 1.排序的概念及其运用 2.插入排序 3.希尔排序 4.选择排序 5.冒泡排序 6.堆排序 7.快速排序 8.归并排序 9.排序算法复杂度及稳定性分析 10.排序选择题练习 常用排序算法的实现:: 1.排序的概念及其运用…...
不愧是2023年就业最难的一年,还好有车企顶着~
就业龙卷风已经来临,以前都说找不到好的工作就去送外卖,但如今外卖骑手行业都已经接近饱和状态了,而且骑手们的学历也不低,本科学历都快达到了30%了,今年可以说是最难找到工作的一年。 像Android 开发行业原本就属于在…...
C/C++之while(do-while)详细讲解
目录 while循环有两个重要组成部分: while 是一个预测试循环 无限循环 do-while 循环 while循环有两个重要组成部分: 进行 true 值或 false 值判断的表达式;只要表达式为 true 就重复执行的语句或块;图 1 显示了 while 循环的…...
SpringCloud学习笔记(一)认识微服务
一、微服务技术栈 二、单体架构和分布式架构的区别 1、单体架构: 将业务的所有功能集中在一个项目中开发,打成一个包进行部署 优点:架构简单,部署成本低缺点:耦合度高 2、分布式架构: 根据业务功能对系统…...
Unity中使用WebSocket (ws://)的方法
WebSocket使得客户端和服务器之间的数据交换变得更加简单,允许服务端主动向客户端推送数据。在WebSocket API中,浏览器和服务器只需要完成一次握手,两者之间就直接可以创建持久性的连接,并进行双向数据传输。 WebSocket与http 其…...
米哈游春招算法岗-2023.03.19-第一题-交换字符-简单题
交换字符Problem Description 米小游拿到了一个仅由小写字母组成的字符串,她准备进行恰好一次操作:交换两个相邻字母,在操作结束后使得字符串的字典序尽可能大。 请你输出最终生成的字符串。 input 一个仅由小写字母组成的字符串,…...
能把爬虫讲的这么透彻的,没有20年功夫还真不行【0基础也能看懂】
前言 可以说很多人学编程,不玩点爬虫确实少了很多意思,不管是业余、接私活还是职业爬虫,爬虫世界确实挺精彩的。 今天来给大家浅谈一下爬虫,目的是让准备学爬虫或者刚开始起步的小伙伴们,对爬虫有一个更深更全的认知…...
springcloud学习总结
springcloud 构建微服务项目步骤 导入依赖编写配置文件开启这个功能 Enablexxx配置类 于2023年2月24日下午17点38分开始学习于2023年3月17日晚上20点26分学完总结代码地址:https://gitee.com/liang-weihao/StudySpringcloud学习笔记地址:https://www.…...
2022年亏损超10亿,告别野蛮成长的众安在线急需新“引擎”
2023年3月21日,众安在线披露了2022年财报,营收233.52亿元,同比增长6.44%;净亏损16.33亿元,去年同期净利润为11.6亿元,同比由盈转亏。 尽管众安在线再次身陷亏损的泥潭,但投资者却没有选择逃离。…...
ChatGPT文心一言逻辑大比拼(一)
❤️觉得内容不错的话,欢迎点赞收藏加关注😊😊😊,后续会继续输入更多优质内容❤️👉有问题欢迎大家加关注私戳或者评论(包括但不限于NLP算法相关,linux学习相关,读研读博…...
【机器学习面试总结】————特征工程
【机器学习面试总结】————特征工程一、特征归一化为什么需要对数值类型的特征做归一化?二、类别型特征在对数据进行预处理时,应该怎样处理类别型特征?三、高维组合特征的处理什么是组合特征?如何处理高维组合特征?四、组合特征怎样有效地找到组合特征?五、文本表示模型…...
如何将字符串反转?
参考答案 使用 StringBuilder 或 StringBuffer 的 reverse 方法,本质都调用了它们的父类 AbstractStringBuilder 的 reverse 方法实现。(JDK1.8)不考虑字符串中的字符是否是 Unicode 编码,自己实现。递归1. public AbstractStrin…...
Linux内核IO基础知识与概念
什么是 IO在计算机操作系统中,所谓的I/O就是 输入(Input)和输出(Output),也可以理解为读(Read)和写(Write),针对不同的对象,I/O模式可以划分为磁盘…...
paper文献和科研小工具
一、好用的网站 Aminer 二、好用的工具 1. SciSpace SciSpace官网 【ChatGPT 论文阅读神器】SciSpace 用户注册与实战测试 SciSpace是一款基于 ChatGPT 的论文阅读神器。 2. ReadPaper 强大且超实用的论文阅读工具——ReadPaper ReadPaper官网 ReadPaper下载链接 Rea…...
dfs和bfs能解决的问题
一.理解暴力穷举之dfs和bfs暴力穷举暴力穷举是在解决问题中最常用的手段,而dfs和bfs算法则是这个手段的两个非常重要的工具。其实,最简单的穷举法是直接遍历,如数列求和,遍历一个数组即可求得所问答案,这与我在前两篇博…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...
