数据结构-二叉树力扣题

目录

1.相同的树

 2.二叉树中查找值为x的节点

3.单值二叉树

4.对称二叉树

 5.二叉树的前序遍历 

6.另一颗树的子树 

层序遍历:

7.二叉树遍历

8.判断二叉树是否是完全二叉树

 一个特殊的性质:


1.相同的树

题目链接:力扣(LeetCode)

思路:

这道题我们可以把它分为三个子问题,分别是:根与根、左子树与左子树、右子树与右子树之间的比较,而且最好是用前序的方式,即先比较根,要是根都不相等,后面的就不用比较了,而子树也可以在再分为根、左子树、右子树......直到不能分为止,所以每次递归调用:如果根的值不相等,就返回false,如果相等,就继续往下比较

注意:要分全为空、只有一个为空、全不为空三种情况处理。

代码如下:

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);
}

 2.二叉树中查找值为x的节点

这道题是延续我们上节内容

思路:

这道题思路很简单,也是分为:查找根、左子树、右子树三个子问题,先找根的值,如果相等就返回根节点,如果不等,继续找左子树,如果相等,返回左子树的节点,如果不相等,继续找右子树,如果相等,返回右子树节点,如果不等,则继续上面过程。

但是这道题我们要求返回的是节点,所以在某次递归中,如果找到了节点,就要先把它保存下来,然后再返回到这次递归的上一级,如果不保存,那节点极大可能返回不到函数外面。总而言之,递归是一级一级往上返回的,如果递归有返回值,每次递归都要确保能接收到下一次递归返回的值。

代码如下:

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail\n");return NULL;}node->left = NULL;node->right = NULL;node->data = x;return node;
}BTNode* CreatBinaryTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}
//二叉树中查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* ret1 = BinaryTreeFind(root->left, x);if (ret1){return ret1;}BTNode* ret2 = BinaryTreeFind(root->right, x);if (ret2){return ret2;}return NULL;
}
int main()
{BTNode* root = CreatBinaryTree();BTNode* p = BinaryTreeFind(root, 3);printf("%d\n", p->data);return 0;
}

3.单值二叉树

题目链接:力扣(LeetCode)

思路:

 这道题,我们可以先比较根节点和左子树的值,然后比较根节点和右子树的值,当左子树不为空且它和根节点的值不相等时,返回false,当右子树不为空且它和根节点的值不相等时,返回false,当左右子树都和根节点相等时,继续递归,直到root==NULL,返回true,这时,true&&true=true,返回true。

代码如下:

bool isUnivalTree(struct TreeNode* root) {if(root==NULL){return true;}if(root->left!=NULL&&root->val!=root->left->val){return false;}if(root->right!=NULL&&root->val!=root->right->val){return false;}return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

4.对称二叉树

题目链接:力扣(LeetCode)

思路:

这道题默认有一个根节点,该节点不用比较所以我们可以比较根节点下的左子树和右子树,这就需要两个参数,我们可以把左子树的根节点和右子树的根节点作为左根和右根传给函数_isSymmetric(),然后把左根的左子树和右根的右子树比较,左根的右子树和右根的左子树比较,如果不等,返回false,如果相等,继续递归,直到全部为空,返回true,true&&true=true,返回true。

代码如下:

bool _isSymmetric(struct TreeNode*leftRoot,struct TreeNode*rightRoot){//全部为空if(leftRoot==NULL&&rightRoot==NULL){return true;}//只有一个为空if(leftRoot==NULL||rightRoot==NULL){return false;}//全不为空if(leftRoot->val!=rightRoot->val){return false;}return _isSymmetric(leftRoot->left,rightRoot->right)&&_isSymmetric(rightRoot->left,leftRoot->right);}
bool isSymmetric(struct TreeNode* root) {return _isSymmetric(root->left,root->right);
}

 5.二叉树的前序遍历 

题目链接:力扣(LeetCode)

思路:

这道题看起来很简单,只需要按照根、左子树、右子树的顺序依次访问即可,但是有很多坑:

1. 需要自己malloc数组,但是数组大小不知道,所以还要写一个函数用来计算二叉树大小

2. malloc数组之后就不能在原函数中写递归了,否则,每次递归都会malloc一个空间,所以又得专门写一个递归的函数。

3.二叉树节点的值要存储到数组中,必然要使用下标,但是下标在调用中不能传值,否则每次递归调用后,栈帧销毁,栈帧中形参i++后的值不能返回上一级递归,往数组中存放数据就会出错。

下面来看一个经典的错误:

int TreeSize(struct TreeNode* root){return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;}void _preorderTraversal(struct TreeNode* root, int*a,int i){if(root==NULL){return;}a[i++]=root->val;_preorderTraversal(root->left,a,i);_preorderTraversal(root->right,a,i);}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize=TreeSize(root);int*a=(int*)malloc(*returnSize*sizeof(int));int i=0;_preorderTraversal(root, a,i);return a;
}

 可以看到,下面用例执行错误了:

为什么呢?

画一下递归调用图就知道了:

所以以后在递归时如果需要传下标,最好传地址,用指针接收。 

正确代码如下:

int TreeSize(struct TreeNode* root){return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;}void _preorderTraversal(struct TreeNode* root, int*a,int* pi){if(root==NULL){return;}a[(*pi)++]=root->val;_preorderTraversal(root->left,a,pi);_preorderTraversal(root->right,a,pi);}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize=TreeSize(root);int*a=(int*)malloc(*returnSize*sizeof(int));int i=0;_preorderTraversal(root, a,&i);return a;
}

6.另一颗树的子树 

思路:

这道题本质还是找两颗相同的树,只不过一个树必须得是另外一个树的子树,那我们可以复用上文中“相同的树”的代码,然后遍历找到第一棵树的所有子树与第二棵树比较,如果不同,继续遍历,只要左右子树中有一个子树与第二颗树相同就返回true。

题目链接:力扣(LeetCode)

代码如下:

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);
}

在讲下一道题之前我们先来学习一下二叉树的层序遍历。

层序遍历:

二叉树的层序遍历是一层一层往下走的,我们可以用队列来实现它,用队列保存二叉树每一层的节点,先让根节点入队,保存并打印根节点的值,然后根节点出队,让它的左右孩子入队,相当于第一层出队的同时带第二层入队,一层带一层,直到队列中所有节点都为NULL,就说明二叉树遍历结束了。

层序需要队列的代码,这里只列出层序的核心代码,关于队列部分的代码,可以在栈与队列章节中找到: 数据结构-栈和队列(一)-CSDN博客

层序代码:

//层序遍历
void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->data);if (front->left)QueuePush(&q,front->left);if (front->right)QueuePush(&q,front->right);}printf("\n");DestoryQueue(&q);
}

注意,这里就是三层嵌套了,队列Queue中有头尾节点和队列大小size,头尾节点中有next指针和数据data,而数据data中存放的是二叉树的节点指针,所以我们在Queue.h中要把数据类型改成二叉树节点指针:

三层嵌套的关系如下图:

所以我们每次pop的都是队列的节点,而front是指向二叉树节点的指针,它没有被pop,所以可以找到二叉树节点的数据和它的左右孩子。

再补充一个内容,那就是二叉树的销毁:

二叉树销毁最好用后序,先销毁左右子树,最后销毁根节点,不建议使用前序,否则先销毁根节点,就找不到左右子树了,又要重新构建二叉树,比较麻烦。

//二叉树的销毁
void BTreeDestory(BTNode* root)
{if (root == NULL){return;}BTreeDestory(root->left);BTreeDestory(root->right);free(root);
}

7.二叉树遍历

题目链接:二叉树遍历_牛客题霸_牛客网

这道题其实包含了二叉树的创建和遍历, 相当于给一个字符串,要求把给字符串恢复成一个二叉树,然后输出它的中序遍历,那abc##de#g##f###,它是前序遍历的,我们就用前序把它恢复成二叉树:

创建二叉树时,也是先创建根节点,然后创建左子树、右子树。

注意:在传数组下标时,传地址,用指针接收。

代码如下:

#include <stdio.h>
#include<stdlib.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail\n");return NULL;}node->left = NULL;node->right = NULL;node->data = x;return node;
}
//创建二叉树
BTNode*CreateTree(char*a,int*pi)
{if(a[*pi]=='#'){(*pi)++;return NULL;}BTNode*root=BuyNode(a[*pi]);(*pi)++;root->left=CreateTree(a,pi);root->right=CreateTree(a,pi);return root;
}
//中序遍历
void InOrder(BTNode*root)
{if(root==NULL){return;}InOrder(root->left);printf("%c ",root->data);InOrder(root->right);}
int main() 
{char a[100];scanf("%s",a);int i=0;BTNode*root=CreateTree(a,&i);InOrder(root);printf("\n");return 0;
}

8.判断二叉树是否是完全二叉树

思路:

 这道题就要使用到层序遍历了,我们说层序遍历是一层带一层的入队和出队的过程,而完全二叉树的每一层都是按顺序排放的,让它的每一层数据入队,然后出队,直到遇见空,如果是完全二叉树,那此时最后一个数据出队后,后面应该全为NULL,而非完全二叉树就不全是NULL了,如下图:

所以当我们遇到空时就跳出循环,然后判断后面的是否全为空,一旦有非空,那就不是完全二叉树。

 代码如下:

//判断二叉树是否是完全二叉树
bool BTreeComplete(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){DestoryQueue(&q);return false;}}DestoryQueue(&q);return true;
}

二叉树的一个特殊的性质:

 对任何一棵二叉树, 如果度为0的叶结点个数为n0 , 度为2的分支结点个数为 n1,则有 n0=n1 +1

 简单推导一下:

对二叉树增加一个度为1的节点就一定会减少一个度为0的节点,同时增加的这个节点度也为0,此时度为0和度为2的节点个数相当于没变:

而增加一个度为2的节点就一定会减少一个度为1的,同时会增加一个度为0的节点:

所以二叉树中度为0的节点总是比度为2的节点个数多一个。 

下面我们来做道题:

在具有 2n 个结点的完全二叉树中,叶子结点个数为( )
A n
B n+1
C n-1
D n/2

答案是:A

假设度为0的节点有n0个,度为1的有n1个,度为2的有n2个,根据上文学过的性质,可得:

n0 + n1 + n0-1=2n,而此时要整除(叶子节点一定是整数个),n1必然是1,所以可得n0 = 2n/2 = n

好了,到今天为止,我们二叉树就告一段落了,其实二叉树还有很多问题,这些留到后面C++的时候学习,

下节内容会接着讲解排序,敬请期待。。。 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/194186.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

DSP生成hex方法

以下使用两种方法生成的HEX文件&#xff0c;亲测可用 &#xff08;1&#xff09;万能法 不管.out文件是哪个版本CCS编译器生成的&#xff0c;只要用HEX2000.exe软件&#xff0c;翻译都可以使用。方法&#xff1a; hex2000 -romwidth 16 -memwidth 16 -i -o 20170817chuankou…

CentOS修改root用户密码

一、适用场景 1、太久没有登录CentOS系统&#xff0c;忘记管理密码。 2、曾经备份的虚拟化OVA或OVF模板&#xff0c;使用模板部署新系统后&#xff0c;忘记root密码。 3、被恶意攻击修改root密码后的紧急修复。 二、实验环境 1、VMware虚拟化的ESXI6.7下&#xff0c;通过曾经…

博物馆信息展示预约小程序的效果如何

随着大环境放开&#xff0c;如博物馆等场所也开始了正常营业&#xff0c;而这些场所在市场中中的需求度很广&#xff0c;每天客流量也相对可观。 但依然发现博物馆痛点所在。 通过【雨科】平台搭建博物馆小程序展示所有内容信息&#xff0c;覆盖微信、百度、头条、抖音、支付宝…

听GPT 讲Rust源代码--library/core/src(8)

题图来自 Hello, crustaceans. File: rust/library/core/src/future/ready.rs 在Rust源代码中&#xff0c;rust/library/core/src/future/ready.rs文件的作用是定义了一个名为Ready的Future类型。Ready是一个简单的Future实现&#xff0c;它立即返回一个给定的值。 Ready 是一个…

[代码实战和详解]VGG16

VGG16 详解 我的github代码实现&#xff1a;vgg16 我们在vgg16神经网络上训练了SIGNS数据集&#xff0c;这是一个分类的数据集&#xff0c;在我的github上有介绍怎么下载数据集以及如何训练。 VGG16是一个卷积神经网络&#xff08;CNN&#xff09;架构&#xff0c;它在2014年…

高防CDN:构筑网络安全的钢铁长城

在当今数字化的世界里&#xff0c;网络安全问题日益突显&#xff0c;而高防CDN&#xff08;高防御内容分发网络&#xff09;正如一座坚不可摧的钢铁长城&#xff0c;成为互联网安全的不可或缺之物。本文将深入剖析高防CDN在网络安全环境中的关键作用&#xff0c;探讨其如何构筑…

linux套接字-Socket

1.概念 局域网和广域网 局域网&#xff1a;局域网将一定区域内的各种计算机、外部设备和数据库连接起来形成计算机通信的私有网络。广域网&#xff1a;又称广域网、外网、公网。是连接不同地区局域网或城域网计算机通信的远程公共网络。IPInternet Protocol&#xff09;&#…

LeetCode热题100——二分查找

二分查找 1. 搜索插入位置2. 搜素二维矩阵3. 在排序数组中查找第一个和最后一个元素位置 1. 搜索插入位置 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 // 题…

一款快速从数据库中提取信息工具

DataMiner 介绍 DataMiner是一款数据库自动抽取工具&#xff0c;用于快速从数据库中提取信息&#xff0c;目前支持 mysql、mssql、oracle、mongodb等数据库&#xff0c;可导出CSV、HTML。 功能 支持对所有数据库数据进行采样&#xff0c;并指定采样数量。 支持对指定数据库…

MIB 6.1810操作系统实验:准备工作(Tools Used in 6.1810)

6.1810 / Fall 2023 实验环境&#xff1a; Ubuntuxv6实验必要的依赖环境能通过make qemu进入系统 $ sudo apt-get update && sudo apt-get upgrade $ sudo apt-get install git build-essential gdb-multiarch qemu-system-misc gcc-riscv64-linux-gnu binutils-ri…

手把手教你搭建属于自己的快递小程序

在数字化时代&#xff0c;小程序已经成为各行各业连接用户、提供服务、创造价值的重要工具。其中&#xff0c;快递寄件小程序因其实用性和广泛的需求&#xff0c;成为很多企业和开发者关注的焦点。本文将详细介绍如何快速创建快递寄件小程序&#xff0c;以及如何利用它实现盈利…

DVWA - 3

文章目录 XSS&#xff08;Dom&#xff09;lowmediumhighimpossible XSS&#xff08;Reflected&#xff09;lowmediumhighimpossible XSS&#xff08;Stored&#xff09;lowmediumhighimpossible XSS&#xff08;Dom&#xff09; XSS 主要基于JavaScript语言进行恶意攻击&#…

创建一个用户test且使用testtab表空间及testtemp临时表空间并授予其权限,密码随意

文章目录 1、连接到数据库2、创建表空间3、创建用户4、授予权限5、测试 1、连接到数据库 sqlplus / as sysdba2、创建表空间 创建testtab表空间 CREATE TABLESPACE testtab DATAFILE /u01/app/oracle/oradata/orcl/testtab.dbf SIZE 50M AUTOEXTEND ON NEXT 5M MAXSIZE …

金融帝国实验室(Capitalism Lab)V10版本即将推出全新公司徽标(2023-11-13)

>〔在即将推出的V10版本中&#xff0c;我们将告别旧的公司徽标&#xff0c;采用全新光鲜亮丽、富有现代气息的设计&#xff0c;与金融帝国实验室&#xff08;Capitalism Lab&#xff09;的沉浸式体验完美互补&#xff01;〕 ————————————— >〔《公司详细信…

基于纵横交叉算法优化概率神经网络PNN的分类预测 - 附代码

基于纵横交叉算法优化概率神经网络PNN的分类预测 - 附代码 文章目录 基于纵横交叉算法优化概率神经网络PNN的分类预测 - 附代码1.PNN网络概述2.变压器故障诊街系统相关背景2.1 模型建立 3.基于纵横交叉优化的PNN网络5.测试结果6.参考文献7.Matlab代码 摘要&#xff1a;针对PNN神…

彩虹桥架构演进之路-性能篇

一、前言 一年前的《彩虹桥架构演进之路》侧重探讨了稳定性和功能性两个方向。在过去一年中&#xff0c;尽管业务需求不断增长且流量激增了数倍&#xff0c;彩虹桥仍保持着零故障的一个状态&#xff0c;算是不错的阶段性成果。而这次的架构演进&#xff0c;主要分享一下近期针对…

PyTorch:张量与矩阵

PyTorch 是一个基于 Python 的科学计算包&#xff0c;专门针对深度学习研究&#xff0c;提供了丰富的工具和库。在 PyTorch 中&#xff0c;张量&#xff08;tensor&#xff09;是深度学习的核心数据结构&#xff0c;它可以看作是可以进行自动微分的多维数组。张量不仅可以代表标…

jQuery【jQuery树遍历、jQuery动画(一)、jQuery动画(二)】(四)-全面详解(学习总结---从入门到深化)

目录 jQuery树遍历 jQuery动画(一) jQuery动画(二) jQuery树遍历 1、 .children() 获得子元素&#xff0c;可以传递一个选择器参数 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-…

单脉冲测角-和差比幅法

和差比幅法单脉冲测角 单脉冲测角的类型阵列接收模型和差波束构造方法和差比幅测角仿真 单脉冲测角的类型 传统的单脉冲测向方法主要有3种&#xff0c;分别是半阵法、加权法和和差比幅法。其实这3种方法都需要形成和波束和差波束&#xff0c;只是波束形成的方法不同&#xff0…

109. 有序链表转化为二叉搜索树

题目 题解 分治。 class Solution:def getMedian(self, left: ListNode, right: ListNode) -> ListNode:找到链表的中间节点slow fast leftwhile fast ! right and fast.next ! right:slow slow.nextfast fast.next.nextreturn slowdef buildTree(self, left: ListNod…