二叉树OJ题汇总

本专栏内容为:leetcode刷题专栏,记录了leetcode热门题目以及重难点题目的详细记录

💓博主csdn个人主页:小小unicorn
⏩专栏分类:Leetcode
🚚代码仓库:小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

二叉树OJ题汇总

  • 判断二叉树是否为完全二叉树
  • 判断二叉树是否为对称二叉树
  • 判断二叉树是否为平衡二叉树
  • 判断二叉树是否为单值二叉树
  • 判断二叉树是另一棵树的子树
  • 判断两颗二叉树是否相同
    • 解题思路:
  • 二叉树的销毁
  • 二叉树的深度遍历(接口型题目)
    • 前序遍历
    • 中序遍历
    • 后序遍历
  • 左叶子之和
    • 解题思路:
    • 代码解决:
  • 二叉树遍历(牛客)
    • 解题思路:
    • 代码解决:

判断二叉树是否为完全二叉树

思路(借助一个队列):
 1.先把根入队列,然后开始从队头出数据。
 2.出队头的数据,把它的左孩子和右孩子依次从队尾入队列(NULL也入队列)。
 3.重复进行步骤2,直到读取到的队头数据为NULL时停止入队列。
 4.检查队列中剩余数据,若全为NULL,则是完全二叉树;若其中有一个非空的数据,则不是完全二叉树。
在这里插入图片描述

//判断二叉树是否是完全二叉树
bool isCompleteTree(BTNode* root)
{
	Queue q;
	QueueInit(&q);//初始化队列
	if (root != NULL)
		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)//若队列中存在非空指针,则不是完全二叉树
		{
			QueueDestroy(&q);//销毁队列
			return false;
		}
	}
	QueueDestroy(&q);//销毁队列
	return true;//若队列中全是空指针,则是完全二叉树
}

判断二叉树是否为对称二叉树

题目来源:101.对称二叉树
题目描述:
给你一个二叉树的根节点 root , 检查它是否轴对称
对称二叉树就是镜像对称。

在这里插入图片描述
要判断某二叉树是否是对称二叉树,则判断其根结点的左子树和右子树是否是镜像对称即可。

因为是镜像对称,所以左子树的遍历方式和右子树的遍历方式是不同的,准确来说,左子树和右子树的遍历是反方向进行的。

//对称二叉树:
bool isSameTree2(BTNode* p, BTNode* q)
{
	//都为空
	if (p == NULL && q == NULL)
	{
		return true;
	}
	//其中一个为空
	if (p == NULL || q == NULL)
	{
		return false;
	}
	//都不为空
	if (p->val != q->val)
	{
		return false;
	}
	return isSameTree2(p->left, q->right) && isSameTree2(p->right, q->left);
}
bool isSymmetric(BTNode* root)
{
	if (root == NULL)
	{
		return true;
	}
	return isSameTree2(root->left, root->right);
}

判断二叉树是否为平衡二叉树

若一棵二叉树的每个结点的左右两个子树的高度差的绝对值不超过1,则称该树为平衡二叉树。
在这里插入图片描述
思路一:
继续拆分子问题:
 1.求出左子树的深度。
 2.求出右子树的深度。
 3.若左子树与右子树的深度差的绝对值不超过1,并且左右子树也是平衡二叉树,则该树是平衡二叉树。

时间复杂度O(N2

//判断二叉树是否是平衡二叉树
bool isBalanced(BTNode* root)
{
	if (root == NULL)//空树是平衡二叉树
		return true;

	int leftDepth = BinaryTreeMaxDepth(root->left);//求左子树的深度
	int rightDepth = BinaryTreeMaxDepth(root->right);//求右子树的深度
	//左右子树高度差的绝对值不超过1 && 其左子树是平衡二叉树 && 其右子树是平衡二叉树
	return abs(leftDepth - rightDepth) < 2 && isBalanced(root->left) && isBalanced(root->right);
}

思路二:
我们可以采用后序遍历:
 1.从叶子结点处开始计算每课子树的高度。(每棵子树的高度 = 左右子树中高度的较大值 + 1)
 2.先判断左子树是否是平衡二叉树。
 3.再判断右子树是否是平衡二叉树。
 4.若左右子树均为平衡二叉树,则返回当前子树的高度给上一层,继续判断上一层的子树是否是平衡二叉树,直到判断到根为止。(若判断过程中,某一棵子树不是平衡二叉树,则该树也就不是平衡二叉树了)

bool _isBalanced(BTNode* root, int* ph)
{
	if (root == NULL)//空树是平衡二叉树
	{
		*ph = 0;//空树返回高度为0
		return true;
	}
	//先判断左子树
	int leftHight = 0;
	if (_isBalanced(root->left, &leftHight) == false)
		return false;
	//再判断右子树
	int rightHight = 0;
	if (_isBalanced(root->right, &rightHight) == false)
		return false;
	//把左右子树的高度中的较大值+1作为当前树的高度返回给上一层
	*ph = Max(leftHight, rightHight) + 1;

	return abs(leftHight - rightHight) < 2;//平衡二叉树的条件
}
//判断二叉树是否是平衡二叉树
bool isBalanced(BTNode* root)
{
	int hight = 0;
	return _isBalanced(root, &hight);
}

判断二叉树是否为单值二叉树

这个题我们可以通过判断二叉树的根与叶子是否相等来解决这个问题,注意要分三种情况:

1.如果是空树,那也是符合情况的,直接返回true。

2.首先满足左子树不为空的条件下,判断左子树的值是否与根相同,相同返回true,不相同返回false.

3.首先满足右子树不为空的条件下,判断右子树的值是否与根相同,相同返回true,不相同返回false.

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

判断二叉树是另一棵树的子树

题目来源:572.另一颗树的子树

判断 subRoot 是否是二叉树 root 的子树,即检验 root 中是否包含和 subRoot 具有相同结构和结点值的子树,其中 root 和 subRoot 均为非空二叉树。
在这里插入图片描述

思路:
 依次判断以 root 中某一个结点为根的子树是否与subRoot相同。
在这里插入图片描述
发现 root 中的某一个子树与 subRoot 相匹配时,便不再继续比较其他子树,所以图中只会比较到序号2就结束比较。

//比较以root和subRoot为根结点的两棵树是否相等
bool Compare(BTNode* root, BTNode* subRoot)
{
	if (root == NULL&&subRoot == NULL)//均为空树,相等
		return true;
	if (root == NULL || subRoot == NULL)//一个为空另一个不为空,不相等
		return false;
	if (root->val != subRoot->val)//结点的值不同,不相等
		return false;
	//比较两棵树的子结点
	return Compare(root->left, subRoot->left) && Compare(root->right, subRoot->right);
}
//另一个树的子树
bool isSubtree(BTNode* root, BTNode* subRoot)
{
	if (root == NULL)//空树,不可能是与subRoot相同(subRoot非空)
		return false;
	if (Compare(root, subRoot))//以root和subRoot为根,开始比较两棵树是否相同
		return true;
	//判断root的左孩子和右孩子中是否有某一棵子树与subRoot相同
	return isSubtree(root->left, subRoot) || isSubtree(root->right,subRoot);
}

判断两颗二叉树是否相同

题目来源:leetcode100.相同的树
题目描述:
给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

解题思路:

判断两棵二叉树是否相同,也可以将其分解为子问题:
 1.比较两棵树的根是否相同。
 2.比较两根的左子树是否相同。
 3.比较两根的右子树是否相同。

 代码如下:

bool isSameTree(BTNode* p, BTNode* 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);
    
}

二叉树的销毁

二叉树的销毁,与其他数据结构的销毁类似,都是一边遍历一边销毁。但是二叉树需要注意销毁结点的顺序,遍历时我们应该选用后序遍历,也就是说,销毁顺序应该为:左子树->右子树->根。

 我们必须先将左右子树销毁,最后再销毁根结点,若先销毁根结点,那么其左右子树就无法找到,也就无法销毁了。

//二叉树销毁
void BinaryTreeDestroy(BTNode* root)
{
	if (root == NULL)
		return;

	BinaryTreeDestroy(root->left);//销毁左子树
	BinaryTreeDestroy(root->right);//销毁右子树
	free(root);//释放根结点
}

二叉树的深度遍历(接口型题目)

接下来所要说的深度遍历与前面会有所不同,我们前面说到的深度遍历是将一棵二叉树遍历,并将遍历结果打印屏幕上(较简单)。

而下面说到的深度遍历是将一棵二叉树进行遍历,并将遍历结果存储到一个动态开辟的数组中,将数组作为函数返回值进行返回。

思路:
 1.首先计算二叉树中结点的个数,便于确定动态开辟的数组的大小。
 2.遍历二叉树,将遍历结果存储到数组中。
 3.返回数组。

前序遍历

题目来源:144.二叉树的前序遍历
代码:

//求树的结点个数
int TreeSize(BTNode* root)
{
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
//将树中结点的值放入数组
void preorder(BTNode* 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(BTNode* root, int* returnSize)
{
	*returnSize = TreeSize(root);//值的个数等于结点的个数
	int* a = (int*)malloc(sizeof(int)*(*returnSize));
	int i = 0;
	preorder(root, a, &i);//将树中结点的值放入数组
	return arr;
}

中序遍历

题目来源:94.二叉树的中序遍历

//求树的结点个数
int TreeSize(BTNode* root)
{
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
//将树中结点的值放入数组
void inorder(BTNode* 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(BTNode* root, int* returnSize)
{
	*returnSize = TreeSize(root);//值的个数等于结点的个数
	int* a = (int*)malloc(sizeof(int)*(*returnSize));
	int i = 0;
	inorder(root, a, &i);//将树中结点的值放入数组
	return arr;
}

后序遍历

题目来源:145.二叉树的后序遍历

//求树的结点个数
int TreeSize(BTNode* root)
{
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
//将树中结点的值放入数组
void postorder(BTNode* 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(BTNode* root, int* returnSize)
{
	*returnSize = TreeSize(root);//值的个数等于结点的个数
	int* a = (int*)malloc(sizeof(int)*(*returnSize));
	int i = 0;
	postorder(root, a, &i);//将树中结点的值放入数组
	return arr;
}

左叶子之和

题目描述:
给定二叉树的根节点 root ,返回所有左叶子之和。
在这里插入图片描述
题目来源:leetcode404.左叶子之和
牛客:NC248.左叶子之和

解题思路:

在解决这个问题之前,我们首先要知道什么是叶子节点:
叶子节点:当前节点没有左孩子也没有右孩子

具体解题思路如下:
首先:
判断是否为空树,
如果是空树,返回0;
如果不是空树,判断左孩子节点是否为左叶子节点
然后继续遍历左子树和右子树中的孩子节点,并把结果累加起来。

代码解决:

int sumOfLeftLeaves(struct TreeNode* root ) 
{
    if(root==NULL)
    {
        return 0;
    }
    int sum=0;
    if(root->left&&root->left->left==NULL&&root->left->right==NULL)
    {
          sum=root->left->val;
    }

    return sum+sumOfLeftLeaves(root->left)+sumOfLeftLeaves(root->right);
}

结果如下:
在这里插入图片描述
在这里插入图片描述

二叉树遍历(牛客)

题目来源:KY11.二叉树遍历(牛客网)

题目描述:
编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。
输入描述:
输入包括1行字符串,长度不超过100。
输出描述:
可能有多组测试数据,对于每组数据, 输出将输入字符串建立二叉树后中序遍历的序列,每个字符后面都有一个空格。 每个输出结果占一行。
在这里插入图片描述

解题思路:

根据前序遍历所得到的字符串,我们可以很容易地将其对应的二叉树画出来。
在这里插入图片描述
其实很容易发现其中的规律,我们可以依次从字符串读取字符:
 1.若该字符不是#,则我们先构建该值的结点,然后递归构建其左子树和右子树。
 2.若该字符是#,则说明该位置之下不能再构建结点了,返回即可。

构建完树后,使用中序遍历打印二叉树的数据即可。

代码解决:

#include <stdio.h>
#include<stdlib.h>

typedef struct BinaryTreeNode
{
      struct BinaryTreeNode*left;
      struct BinaryTreeNode*right;
      int val;  
}BTNode;

BTNode*GreateTree(char*str,int*pi)
{
    if(str[*pi]=='#')
    {
        (*pi)++;
        return NULL;
    }

    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    root->val=str[*pi];
    (*pi)++;

    root->left=GreateTree(str, pi);
    root->right=GreateTree(str, pi);
    
     return root;
}

void Inorder(BTNode*root)
{
  if(root==NULL)
  {
    return ;
  }

  Inorder(root->left);
  printf("%c ",root->val);
  Inorder(root->right);

}

int main() 
{
    char str[100];
    scanf("%s",str);

    int i=0;
    BTNode*root=GreateTree(str, &i);
    Inorder(root);
    return 0;
}

测试结果:
在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

奇偶校验码和循环冗余码

在数据链路层的传输中&#xff0c;1可能变成0&#xff0c;0可能变成1&#xff0c;这是比特差错。 为了应对比特差错&#xff0c;有两种方式&#xff0c;即自动重传请求ARQ&#xff08;Automatic Repeat-reQuest&#xff09;和前向纠错FEC&#xff08;Forward Error Correction&…

c++获取和设置环境变量

这个功能非常常用&#xff0c;但是容易忘记&#xff0c;这里做个记录。 注意&#xff0c;设置的环境变量只在当前进程中生效&#xff0c;所以在电脑中的环境变量设置区域看不到。 std::string env getenv("PATH");env "X:\\envtest";std::string newEnv…

亚马逊、美客多卖家测评:如何建立养号团队实现运营化式测评?

大家好&#xff0c;我是跨境电商测评养号7年从事经验的珑哥。养号环境软件开发&#xff0c;深度解决各跨境平台矩阵养号防关联、砍单、F号问题。关注珑哥解决更多跨境养号测评问题。 测评&#xff0c;相信这个词对于大部分跨境卖家来说&#xff0c;想必都不陌生&#xff0c;因…

LCR 166.珠宝的最高价值 + 动态规划 + 记忆化搜索 + 递推 + 空间优化

LCR 166. 珠宝的最高价值 - 力扣&#xff08;LeetCode&#xff09; 现有一个记作二维矩阵 frame 的珠宝架&#xff0c;其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为&#xff1a; 只能从架子的左上角开始拿珠宝每次可以移动到右侧或下侧的相邻位置到达珠宝架子的右下…

什么是OTP认证?OTP认证服务器有哪些应用场景?

OTP是一次性密码&#xff0c;即只能使用一次的密码。它基于专门的算法&#xff0c;每隔60秒生成一个不可预测的随机数字组合。这种密码的有效期仅在一次会话或交易过程中&#xff0c;因此不容易受到重放攻击。在计算器系统或其他数字设备上&#xff0c;OTP是一种只能使用一次的…

Spring Boot 3 整合 xxl-job 实现分布式定时任务调度,结合 Docker 容器化部署(图文指南)

目录 前言初始化数据库Docker 部署 xxl-job下载镜像创建容器并运行访问调度中心 SpringBoot 整合 xxl-jobpom.xmlapplication.ymlXxlJobConfig.java执行器注册查看 定时任务测试添加测试任务配置定时任务测试结果 结语附录xxl-job 官方文档xxl-job 源码测试项目源码 前言 xxl-…

【VR开发】【Unity】【VRTK】3-VR项目设置

任何VR避不开的步骤 如何设置VR项目,无论是PC VR还是安卓VR,我在不同的系列教程中都说过了,不过作为任何一个VR开发教程都难以避免的一环,本篇作为VRTK的开发教程还是对VR项目设置交代一下。 准备好你的硬件 头盔必须是6DoF的,推荐Oculus Quest系列,Rift系列,HTC和Pi…

3.字符集和比较规则简介

3.字符集和比较规则简介 1.字符集和比较规则简介1.1 字符集简介1.2 比较规则简介1.3 一些重要的比较规则 2. MySQL 中支持的字符集和比较规则2.1 MySQL 的 utf8 和 utf8mb42.2 字符集查看2.3 比较规则查看 3. 字符集和比较规则的应用3.1 各级别的字符集和比较规则1. 服务器级别…

基于深度学习的植物识别算法 - cnn opencv python 计算机竞赛

文章目录 0 前言1 课题背景2 具体实现3 数据收集和处理3 MobileNetV2网络4 损失函数softmax 交叉熵4.1 softmax函数4.2 交叉熵损失函数 5 优化器SGD6 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; **基于深度学习的植物识别算法 ** …

【设计模式】第6节:创建型模式之“原型模式”

由于本人现在所使用的语言主要是golang&#xff0c;所以后面的代码主要使用golang编写。语言实现应该不是障碍&#xff0c;主要是理解每种设计模式它的思想。 如果对象的创建成本比较大&#xff0c;而同一个类的不同对象之间差别不大&#xff08;大部分字段都相同&#xff09;…

Google play开发者账号注册的实用技巧与建议——身份验证、付款资料、支付成功注册失败?

总所周知&#xff0c;如果要在Google paly应用商店上发布应用&#xff0c;需要先注册谷歌开发者账号。但随着发展&#xff0c;谷歌对开发者账号的审核越来越严格&#xff0c;要求越来越多&#xff0c;账号注册通过率越来越低&#xff0c;频繁被封&#xff0c;令开发者们苦恼不已…

AD9371 官方例程HDL JESD204B相关IP端口信号

AD9371 系列快速入口 AD9371ZCU102 移植到 ZCU106 &#xff1a; AD9371 官方例程构建及单音信号收发 ad9371_tx_jesd -->util_ad9371_xcvr接口映射&#xff1a; AD9371 官方例程之 tx_jesd 与 xcvr接口映射 AD9371 官方例程 时钟间的关系与生成 &#xff1a; AD9371 官方…

项目实战:修改水果库存系统特定库存记录

1、在edit.html修改库存页面添加点击事件 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title><link rel"stylesheet" href"style/index.css"><script s…

基于B样条的FFD自由变换原理与C++实现

原理&#xff1a; https://blog.csdn.net/shandianfengfan/article/details/113706496 https://blog.csdn.net/qq_38517015/article/details/99724916 https://blog.csdn.net/qq_38517015/article/details/99724916 三次B样条 cubicBSplineFFD .h #pragma once #include &quo…

Unity在Project右键点击物体之后获取到点击物体的名称

Unity在Project右键点击物体之后获取到点击物体的名称 描述&#xff1a; 在Unity的Project右键点击物体之后选择对应的菜单选项点击之后打印出物体的名称 注意事项 如果获取到文件或者预制体需要传递objcet类型&#xff0c;然后使用 GameObject.Instantiate((GameObject)se…

vue-advanced-chat使用指南

demo地址:— vue-advanced-chat的git地址:https://github.com/advanced-chat/vue-advanced-chat 1.搭建demo demo地址克隆后在demo目录安装依赖并启动 启动之后的页面如下: 2.前端代码分析 2.1 重点api分析 current-user-id:当前用户id room-id:可随时加载特定房间?…

Rhino 8 for Mac(犀牛8)中文激活版

Rhino 8是一款功能强大的三维构建软件&#xff0c;它可以帮助用户创建各种类型的3D模型&#xff0c;包括产品设计、建筑设计、工业设计计划等。Rhino 7具有直观的界面和丰富的工具库&#xff0c;让用户可以快速轻松地进行建模、编辑、分析和漂染。 Rhino 8支持多种文件格式的导…

回归预测 | Matlab实现POA-CNN-SVM鹈鹕算法优化卷积神经网络-支持向量机多变量回归预测

Matlab实现POA-CNN-SVM鹈鹕算法优化卷积神经网络-支持向量机多变量回归预测 目录 Matlab实现POA-CNN-SVM鹈鹕算法优化卷积神经网络-支持向量机多变量回归预测效果一览基本介绍程序设计参考资料 效果一览 基本介绍 1.POA-CNN-SVM鹈鹕算法优化卷积神经网络-支持向量机的多变量回归…

多测师肖sir___app测试_001

app测试 一、app测试分为两大类 app手工测试&#xff08;讲&#xff09; app自动化测试&#xff08;讲&#xff09; &#xff08;1&#xff09;手工app测试&#xff1f; 就是通过手点击app上的应用&#xff0c;cs架构上 &#xff08;2&#xff09;app自动化测试&#xff1f; 通…