leetcode及牛客网二叉树相关题、单值二叉树、相同的树、二叉树的前序、中序、后序遍历、另一棵树的子树、二叉树的遍历、 对称二叉树等的介绍
文章目录
- 前言
- 一、单值二叉树
- 二、相同的树
- 三、二叉树的前序遍历
- 四、二叉树的中序遍历
- 五、二叉树的后序遍历
- 六、另一棵树的子树
- 七、二叉树的遍历
- 八、 对称二叉树
- 总结
前言
leetcode及牛客网二叉树相关题、单值二叉树、相同的树、二叉树的前序、中序、后序遍历、另一棵树的子树、二叉树的遍历、 对称二叉树等的介绍
一、单值二叉树
leetcode原题: 单值二叉树

/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
bool isUnivalTree(struct TreeNode* root) {if(root == NULL)return true;if(root->left != NULL && root->left->val != root->val )return false;if(root->right != NULL && root->right->val != root->val)return false;return isUnivalTree(root->left) && isUnivalTree(root->right);
}
- 递归思想:
- 每个节点都分别与它的左子树根节点和右子树根节点比较。
- 若传入的节点为NULL,返回 true。(不违反相同的规则)
- 若左右子树分别不为空并且分别不等于根节点则返回 false。
二、相同的树
leetcode原题:相同的树

/*** Definition for a binary tree node.* 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 || p != NULL && q == NULL){return false;}if(p->val != q->val){return false;}return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
- 递归思想:
- 两棵树同时按照根节点,左子树,右子树的顺序比较每个节点。
- 若两个树根节点都为NULL,则返回true。
- 若两棵树根节点只有一个为NULL,则返回false。
- 若两棵树根节点的值不相等,则返回false。
三、二叉树的前序遍历
leetcode原题: 二叉树的前序遍历
- 其中returnSize是数组元素的个数。传入的是数组元素个数的指针。
- 要求返回一个数组。

/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/int TreeSize(struct TreeNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}void preorder(struct TreeNode* root, int* a, int* pi)
{if(root == NULL)return;a[(*pi)++] = root->val;preorder(root->left, a, pi);preorder(root->right, a, pi);
}int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = TreeSize(root);int* a = (int*)malloc(*returnSize * sizeof(int));int i = 0;preorder(root, a, &i);return a;
}
- 思想:
- 先求出这个树的节点个数,赋值给returnSize。
- 动态申请returnSize个空间,同时定义下标变量。
- 在函数preorder中采用前序遍历,将每个节点的值依次赋值给数组。
四、二叉树的中序遍历
leetcode原题: 二叉树的前序遍历

/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/int TreeSize(struct TreeNode* root)
{return root == NULL? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}void inorder(struct TreeNode* root, int* a, int* pi)
{if(root == NULL)return;inorder(root->left, a, pi);a[(*pi)++] = root->val;inorder(root->right, a, pi);
}int* inorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = TreeSize(root);int* a = (int*)malloc(*returnSize * sizeof(int));int i = 0;inorder(root, a, &i);return a;
}
五、二叉树的后序遍历
leetcode原题: 二叉树的中序遍历

/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/int TreeSize(struct TreeNode* root)
{return root==NULL? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}void postorder(struct TreeNode* root, int* a, int* pi)
{if(root == NULL)return;postorder(root->left, a, pi);postorder(root->right, a, pi);a[(*pi)++] = root->val;
}int* postorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = TreeSize(root);int* a = (int*)malloc(*returnSize * sizeof(int));int i = 0;postorder(root, a, &i);return a;
}
六、另一棵树的子树
leetcode原题: 另一棵树的子树

/*** Definition for a binary tree node.* 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;return isSameTree(p->left, q->left) && 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);
}
- 将原二叉树与给定子树进行比较。
- 若相同返回true。
- 若不同,原二叉树的左子树和右子树分别与给定子树比较。有一个相同则返回true。
七、二叉树的遍历
牛客网原题: 二叉树的遍历

#include <stdio.h>
#include <stdlib.h>typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType val;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
} BTNode;BTNode* preorder(char* arr, int* pi)
{if(arr[*pi] == '#'){(*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));root->val = arr[(*pi)++];root->left = preorder(arr, pi);root->right = preorder(arr, pi);return root;
}void Inorder(BTNode* root)
{if(root == NULL)return;Inorder(root->left);printf("%c ", root->val);Inorder(root->right);
}int main() {char arr[100] = {0};scanf("%s", arr);int i = 0;BTNode* root = preorder(arr, &i);Inorder(root);return 0;
}
八、 对称二叉树
leetcode原题: 对称二叉树

/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/bool order(struct TreeNode* lret, struct TreeNode* rret)
{if(lret == NULL && rret == NULL)return true;if(lret == NULL || rret == NULL)return false;if(lret->val != rret->val)return false;return order(lret->left, rret->right) && order(lret->right, rret->left);}bool isSymmetric(struct TreeNode* root) {if(root == NULL)return true;return order(root->left, root->right);}
- 如若传入根节点是空树,则返回true。
- 若不是空树,比较它的左右子树。
-
- 若左右子树都是空,则返回true。
-
- 若左右子树只有一个是空,则返回false。
- 然后判断当前两个树节点的val是否相等,若不相等返回false。
- 若相等继续找子树。
总结
leetcode及牛客网二叉树相关题、单值二叉树、相同的树、二叉树的前序、中序、后序遍历、另一棵树的子树、二叉树的遍历、 对称二叉树等的介绍
相关文章:
leetcode及牛客网二叉树相关题、单值二叉树、相同的树、二叉树的前序、中序、后序遍历、另一棵树的子树、二叉树的遍历、 对称二叉树等的介绍
文章目录 前言一、单值二叉树二、相同的树三、二叉树的前序遍历四、二叉树的中序遍历五、二叉树的后序遍历六、另一棵树的子树七、二叉树的遍历八、 对称二叉树总结 前言 leetcode及牛客网二叉树相关题、单值二叉树、相同的树、二叉树的前序、中序、后序遍历、另一棵树的子树、…...
Spring (38)Spring Cloud
Spring Cloud是一系列框架的集合,它利用Spring Boot的开发便利性,简化了分布式系统(如配置管理、服务发现、断路器、路由、微代理、事件总线、全局锁、决策竞选、分布式会话等)的开发。Spring Cloud为开发人员提供了在分布式系统中…...
MySQL之数据库相关操作学习笔记(一)
数据库相关操作 数据库表创建 定义逻辑库、数据表 DML 添加修改删除查询 DCL 用户权限事务 DDL 逻辑库数据表视图索引 DCL (Data Control Language) 示例 DCL(数据控制语言)主要用于控制数据库用户的访问权限和管理事务。DCL 主要包含两类语句&…...
【Node】node的Events模块(事件模块)的介绍和使用
文章目录 简言EventsPassing arguments and this to listeners 向监听器传递参数Asynchronous vs. synchronous 异步和同步Handling events only once 只一次处理事件Error events 错误事件Capture rejections of promises 捕捉拒绝承诺的情况Class: EventEmitter 事件类Event:…...
C#中字节数组(byte[])末尾继续添加字节的示例
方法一:使用List 使用List可以很容易地在末尾添加字节,然后如果需要,可以将其转换回byte[]。 using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Lin…...
Socket编程学习笔记之TCP与UDP
Socket: Socket是什么呢? 是一套用于不同主机间通讯的API,是应用层与TCP/IP协议族通信的中间软件抽象层。 是一组接口。在设计模式中,Socket其实就是一个门面模式,它把复杂的TCP/IP协议族隐藏在Socket接口后面&#…...
JavaScript第九讲BOM编程的练习题
前言 上一节有BOM的讲解,有需要的码客们可以去看一下 以下是一个结合了上述BOM(Browser Object Model)相关内容的练习题及其源代码示例: 练习题: 编写一个JavaScript脚本,该脚本应该执行以下操作&#…...
JavaScript 中创建函数的多种方式
在 JavaScript 中,可以通过多种方式创建函数。每种方式都有其特定的用途、优点和缺点,以及适用的使用场景。以下是几种常见的创建函数的方式及其详细说明。 1. 函数声明(Function Declaration) 示例 function add(a, b) {retur…...
对称二叉树[简单]
优质博文:IT-BLOG-CN 一、题目 给你一个二叉树的根节点root, 检查它是否轴对称。 示例 1: 输入:root [1,2,2,3,4,4,3] 输出:true 示例 2: 输入:root [1,2,2,null,3,null,3] 输出…...
判断GIF类型并使用ImageDecoder解析GIF图
一、判断是否为GIF图片类型 在JavaScript中,判断用户上传的文件是否为GIF文件类型时,通常可以通过检查文件的type属性或文件的拓展名来判断,但是由于文件拓展名可以轻易被用户修改,type属性是由浏览器根据文件拓展名猜测得出的&a…...
数组对象数据修改后页面没有更新,无法进行编辑,校验失效问题
在 Vue 中,当你通过 Object.assign 或其他方式修改了对象中的某个属性时,Vue 并不会触发组件重新渲染,因此表单中的 input 框无法及时更新。这可能导致在修改表单数据后,页面没有更新,而且表单校验也失效的情况。这是因…...
什么是低代码?有什么特点?
低代码是一种高效的软件开发方法,它允许开发者通过图形化界面和预构建的代码块,以最小化传统手写代码的方式快速构建应用程序。这种方法旨在加速应用程序的开发周期,同时降低技术门槛和成本。以下是根据驰骋低代码设计者的观念与主张…...
Kafka 消息保留时长由 24 小时变更为 72 小时的影响分析
目录 Kafka 消息保留时长由 24 小时变更为 72 小时的影响分析Kafka 消息存储机制保留时长对生产速度的影响保留时长对消费速度的影响底层分析与优化建议附加:将 Kafka 消息保留时长从 24 小时更改为 72 小时后,CPU 使用率从 40% 上升到 70% 的现象1. 增加…...
MySQL A表的字段值更新为B表的字段值
MySQL A表的字段值更新为B表的字段值 准备数据表 create table person (id int unsigned auto_increment comment 主键 primary key,uuid varchar(32) not null comment 系统唯一标识符32个长度的字符串,mobile varchar(11) null comment 中国国内手机号,nickn…...
TCP 建链(三次握手)和断链(四次握手)
TCP 建链(三次握手)和断链(四次挥手) 背景简介建链(三次握手)断链(四次挥手)序号及标志位延伸问题为什么建立连接需要握手三次,两次行不行?三次握手可以携带数…...
SpringBoot集成JOOQ加Mybatis-plus使用@Slf4j日志
遇到个问题记录下,就是SpringBoot使用Mybatis和Mybatis-plus时可以正常打印日志,但是JOOQ的操作日志确打印不出来? 下面的解决方法就是将JOOQ的日志单独配置出来,直接给你们配置吧! 在项目的resources目录下创建日志…...
浅谈JavaScript中的对象赋值
目录 常见的对象赋值方式 直接赋值和对象扩展(浅拷贝)两种赋值方式区别 区别 联系 常见的对象赋值方式 1. 直接赋值:this.info this.deviceInfo,将一个对象的引用赋给另一个变量,它们引用同一个对象。 2. 对象扩…...
Java面试题-集合
Java面试题-集合 1、什么是集合?2、集合和数组的区别是什么?3、集合有哪些特点?4、常用的集合类有哪些?5、List, Set, Map三者的区别?6、说说集合框架底层数据结构?7、线程安全的集合…...
从当当网批量获取图书信息
爬取当当网图书数据并保存到本地,使用request、lxml的etree模块、pandas保存数据为excel到本地。 爬取网页的url为: http://search.dangdang.com/?key{}&actinput&page_index{} 其中key为搜索关键字,page_index为页码。 爬取的数据…...
python爬虫之JS逆向——网页数据解析
目录 一、正则 1 正则基础 元字符 基本使用 通配符: . 字符集: [] 重复 位置 管道符和括号 转义符 转义功能 转义元字符 2 正则进阶 元字符组合(常用) 模式修正符 re模块的方法 有名分组 compile编译 二、bs4 1 四种对象 2 导航文档树 嵌套选择 子节点、…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
自然语言处理——文本分类
文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益(IG) 分类器设计贝叶斯理论:线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别, 有单标签多类别文本分类和多…...
二维FDTD算法仿真
二维FDTD算法仿真,并带完全匹配层,输入波形为高斯波、平面波 FDTD_二维/FDTD.zip , 6075 FDTD_二维/FDTD_31.m , 1029 FDTD_二维/FDTD_32.m , 2806 FDTD_二维/FDTD_33.m , 3782 FDTD_二维/FDTD_34.m , 4182 FDTD_二维/FDTD_35.m , 4793...
基于单片机的宠物屋智能系统设计与实现(论文+源码)
本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢,连接红外测温传感器,可实时精准捕捉宠物体温变化,以便及时发现健康异常;水位检测传感器时刻监测饮用水余量,防止宠物…...
pgsql:还原数据库后出现重复序列导致“more than one owned sequence found“报错问题的解决
问题: pgsql数据库通过备份数据库文件进行还原时,如果表中有自增序列,还原后可能会出现重复的序列,此时若向表中插入新行时会出现“more than one owned sequence found”的报错提示。 点击菜单“其它”-》“序列”,…...
