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

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。
  • 若不是空树,比较它的左右子树。
    1. 若左右子树都是空,则返回true。
    1. 若左右子树只有一个是空,则返回false。
  • 然后判断当前两个树节点的val是否相等,若不相等返回false。
  • 若相等继续找子树。

总结

leetcode及牛客网二叉树相关题、单值二叉树、相同的树、二叉树的前序、中序、后序遍历、另一棵树的子树、二叉树的遍历、 对称二叉树等的介绍

相关文章:

leetcode及牛客网二叉树相关题、单值二叉树、相同的树、二叉树的前序、中序、后序遍历、另一棵树的子树、二叉树的遍历、 对称二叉树等的介绍

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

Spring (38)Spring Cloud

Spring Cloud是一系列框架的集合&#xff0c;它利用Spring Boot的开发便利性&#xff0c;简化了分布式系统&#xff08;如配置管理、服务发现、断路器、路由、微代理、事件总线、全局锁、决策竞选、分布式会话等&#xff09;的开发。Spring Cloud为开发人员提供了在分布式系统中…...

MySQL之数据库相关操作学习笔记(一)

数据库相关操作 数据库表创建 定义逻辑库、数据表 DML 添加修改删除查询 DCL 用户权限事务 DDL 逻辑库数据表视图索引 DCL (Data Control Language) 示例 DCL&#xff08;数据控制语言&#xff09;主要用于控制数据库用户的访问权限和管理事务。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[])末尾继续添加字节的示例

方法一&#xff1a;使用List 使用List可以很容易地在末尾添加字节&#xff0c;然后如果需要&#xff0c;可以将其转换回byte[]。 using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Lin…...

Socket编程学习笔记之TCP与UDP

Socket&#xff1a; Socket是什么呢&#xff1f; 是一套用于不同主机间通讯的API&#xff0c;是应用层与TCP/IP协议族通信的中间软件抽象层。 是一组接口。在设计模式中&#xff0c;Socket其实就是一个门面模式&#xff0c;它把复杂的TCP/IP协议族隐藏在Socket接口后面&#…...

JavaScript第九讲BOM编程的练习题

前言 上一节有BOM的讲解&#xff0c;有需要的码客们可以去看一下 以下是一个结合了上述BOM&#xff08;Browser Object Model&#xff09;相关内容的练习题及其源代码示例&#xff1a; 练习题&#xff1a; 编写一个JavaScript脚本&#xff0c;该脚本应该执行以下操作&#…...

JavaScript 中创建函数的多种方式

在 JavaScript 中&#xff0c;可以通过多种方式创建函数。每种方式都有其特定的用途、优点和缺点&#xff0c;以及适用的使用场景。以下是几种常见的创建函数的方式及其详细说明。 1. 函数声明&#xff08;Function Declaration&#xff09; 示例 function add(a, b) {retur…...

对称二叉树[简单]

优质博文&#xff1a;IT-BLOG-CN 一、题目 给你一个二叉树的根节点root&#xff0c; 检查它是否轴对称。 示例 1&#xff1a; 输入&#xff1a;root [1,2,2,3,4,4,3] 输出&#xff1a;true 示例 2&#xff1a; 输入&#xff1a;root [1,2,2,null,3,null,3] 输出&#xf…...

判断GIF类型并使用ImageDecoder解析GIF图

一、判断是否为GIF图片类型 在JavaScript中&#xff0c;判断用户上传的文件是否为GIF文件类型时&#xff0c;通常可以通过检查文件的type属性或文件的拓展名来判断&#xff0c;但是由于文件拓展名可以轻易被用户修改&#xff0c;type属性是由浏览器根据文件拓展名猜测得出的&a…...

数组对象数据修改后页面没有更新,无法进行编辑,校验失效问题

在 Vue 中&#xff0c;当你通过 Object.assign 或其他方式修改了对象中的某个属性时&#xff0c;Vue 并不会触发组件重新渲染&#xff0c;因此表单中的 input 框无法及时更新。这可能导致在修改表单数据后&#xff0c;页面没有更新&#xff0c;而且表单校验也失效的情况。这是因…...

什么是低代码?有什么特点?

低代码是一种高效的软件开发方法&#xff0c;它允许开发者通过图形化界面和预构建的代码块&#xff0c;以最小化传统手写代码的方式快速构建应用程序。这种方法旨在加速应用程序的开发周期&#xff0c;同时降低技术门槛和成本。以下是根据驰骋低代码设计者的观念与主张&#xf…...

Kafka 消息保留时长由 24 小时变更为 72 小时的影响分析

目录 Kafka 消息保留时长由 24 小时变更为 72 小时的影响分析Kafka 消息存储机制保留时长对生产速度的影响保留时长对消费速度的影响底层分析与优化建议附加&#xff1a;将 Kafka 消息保留时长从 24 小时更改为 72 小时后&#xff0c;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 建链&#xff08;三次握手&#xff09;和断链&#xff08;四次挥手&#xff09; 背景简介建链&#xff08;三次握手&#xff09;断链&#xff08;四次挥手&#xff09;序号及标志位延伸问题为什么建立连接需要握手三次&#xff0c;两次行不行&#xff1f;三次握手可以携带数…...

SpringBoot集成JOOQ加Mybatis-plus使用@Slf4j日志

遇到个问题记录下&#xff0c;就是SpringBoot使用Mybatis和Mybatis-plus时可以正常打印日志&#xff0c;但是JOOQ的操作日志确打印不出来&#xff1f; 下面的解决方法就是将JOOQ的日志单独配置出来&#xff0c;直接给你们配置吧&#xff01; 在项目的resources目录下创建日志…...

浅谈JavaScript中的对象赋值

目录 常见的对象赋值方式 直接赋值和对象扩展&#xff08;浅拷贝&#xff09;两种赋值方式区别 区别 联系 常见的对象赋值方式 1. 直接赋值&#xff1a;this.info this.deviceInfo&#xff0c;将一个对象的引用赋给另一个变量&#xff0c;它们引用同一个对象。 2. 对象扩…...

Java面试题-集合

Java面试题-集合 1、什么是集合&#xff1f;2、集合和数组的区别是什么&#xff1f;3、集合有哪些特点&#xff1f;4、常用的集合类有哪些&#xff1f;5、List&#xff0c; Set&#xff0c; Map三者的区别&#xff1f;6、说说集合框架底层数据结构&#xff1f;7、线程安全的集合…...

从当当网批量获取图书信息

爬取当当网图书数据并保存到本地&#xff0c;使用request、lxml的etree模块、pandas保存数据为excel到本地。 爬取网页的url为&#xff1a; http://search.dangdang.com/?key{}&actinput&page_index{} 其中key为搜索关键字&#xff0c;page_index为页码。 爬取的数据…...

python爬虫之JS逆向——网页数据解析

目录 一、正则 1 正则基础 元字符 基本使用 通配符: . 字符集: [] 重复 位置 管道符和括号 转义符 转义功能 转义元字符 2 正则进阶 元字符组合(常用) 模式修正符 re模块的方法 有名分组 compile编译 二、bs4 1 四种对象 2 导航文档树 嵌套选择 子节点、…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

基于单片机的宠物屋智能系统设计与实现(论文+源码)

本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢&#xff0c;连接红外测温传感器&#xff0c;可实时精准捕捉宠物体温变化&#xff0c;以便及时发现健康异常&#xff1b;水位检测传感器时刻监测饮用水余量&#xff0c;防止宠物…...

大数据治理的常见方式

大数据治理的常见方式 大数据治理是确保数据质量、安全性和可用性的系统性方法&#xff0c;以下是几种常见的治理方式&#xff1a; 1. 数据质量管理 核心方法&#xff1a; 数据校验&#xff1a;建立数据校验规则&#xff08;格式、范围、一致性等&#xff09;数据清洗&…...

js 设置3秒后执行

如何在JavaScript中延迟3秒执行操作 在JavaScript中&#xff0c;要设置一个操作在指定延迟后&#xff08;例如3秒&#xff09;执行&#xff0c;可以使用 setTimeout 函数。setTimeout 是JavaScript的核心计时器方法&#xff0c;它接受两个参数&#xff1a; 要执行的函数&…...