数据结构——二叉树提升

2023-09-16 23:35:44

在这里插入图片描述

二叉树题型练习

前言

现在我们开始一轮新的自我提升吧！
二叉树的题目当然也更有难度！
没有什么是生来就会的，尤其是代码这一方面
更是讲究熟能生巧，现在的我们学习代码编程就像婴儿学习灵活使用双手一般
相信以后的我们也可以像使用双手一般毫无困难地编写程序！

一、节点个数以及高度等

// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

size保存的是代码执行到当前位置符合条件的节点个数
1.节点个数代码实现

int TreeSize(BTNode* root) {
	static int size = 0;
	if (root == NULL)
		return 0;
	else
		++size;
	TreeSize(root->left);
	TreeSize(root->right);
	return size;
}

思路解析：
在这里插入图片描述
在这里插入图片描述
2.叶子节点个数代码实现

int TreeLeafSize(BTNode* root) {
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right) {
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

思路解析：
在这里插入图片描述
3.第k层节点个数代码实现

int TreeKLevel(BTNode* root,int k) {
	assert(k > 0);
	if (root == NULL)
		return 0;
	if (k == 1) {
		return 1;
	}
	return TreeKLevel(root->left,k-1) + TreeKLevel(root->right,k-1);
}

思路解析
在这里插入图片描述
4.查找值为x的结点

BTNode* TreeFind(BTNode* root, int x) {
	if (root == NULL)
		return NULL;
	if (root->val == x)
		return root;
	BTNode* ret = NULL;
	ret = TreeFind(root->left, x);
	if (ret)
		return ret;
	ret = TreeFind(root->right, x);
	if (ret)
		return ret;
	return NULL;
}

思路解析
在这里插入图片描述

二、二叉树OJ题

二叉树的前序遍历

题目链接：OJ链接
在这里插入图片描述在这里插入图片描述在这里插入图片描述

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

思路解析
此题要保存节点，所以需要先获取节点个数，然后进行前序遍历，保存每一个节点值。
代码实现：

int TreeSize(struct TreeNode* root){
    return root!=NULL?1+TreeSize(root->left)+TreeSize(root->right):0;
}

void PreOrder(struct TreeNode* root,int*arr,int*i){
    if(root==NULL){
        return;
    }
    arr[(*i)++]=root->val;
    PreOrder(root->left,arr,i);
    PreOrder(root->right,arr,i);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int n=TreeSize(root);
    int* arr=(int*)malloc(sizeof(int)*n);
    int m=0;
    PreOrder(root,arr,&m);
    *returnSize=n;
    return arr;
}

图例解析
在这里插入图片描述

二叉树的中序遍历

题目链接：OJ链接
在这里插入图片描述

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

思路解析
解题思路同上题，遍历时进行中序遍历
代码实现：

int TreeSize(struct TreeNode* root){
    return root==NULL?0:1+TreeSize(root->left)+TreeSize(root->right);
}

void MidOrder(struct TreeNode* root,int*arr,int*i){
    if(root==NULL)
        return;
    MidOrder(root->left,arr,i);
    arr[(*i)++]=root->val;
    MidOrder(root->right,arr,i);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int n=TreeSize(root);
    *returnSize=n;
    int*arr=(int*)malloc(sizeof(int)*n);
    int m=0;
    MidOrder(root,arr,&m);
    return arr;
}

图例解析
在这里插入图片描述

二叉树的后序遍历

题目链接：OJ链接
在这里插入图片描述

提示：

树中节点的数目在范围 [0, 100] 内
-100 <= Node.val <= 100

思路解析
解题思路同上题，遍历时进行后序遍历
代码实现：

int TreeSize(struct TreeNode* root){
    return root==NULL?0:1+TreeSize(root->left)+TreeSize(root->right);
}

void LastOrder(struct TreeNode* root,int*arr,int*i){
    if(root==NULL)
        return;
    LastOrder(root->left,arr,i);
    LastOrder(root->right,arr,i);
      arr[(*i)++]=root->val;
}

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int n=TreeSize(root);
    *returnSize=n;
    int*arr=(int*)malloc(sizeof(int)*n);
    int m=0;
    LastOrder(root,arr,&m);
    return arr;
}

图例解析
在这里插入图片描述

单值二叉树

题目链接：OJ链接
在这里插入图片描述在这里插入图片描述

提示：

给定树的节点数范围是 [1, 100]。
每个节点的值都是整数，范围为 [0, 99] 。

思路解析
遍历二叉树，并且每一个节点值都和根节点的值进行比对，如果不等于根节点的值，则不是单值树。

代码实现：

bool isUnivalTree(struct TreeNode* 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);
}

图例解析
在这里插入图片描述

二叉树最大深度

题目链接：OJ链接
在这里插入图片描述在这里插入图片描述

提示：

树中节点的数量在 [0, 104] 区间内。
-100 <= Node.val <= 100

思路解析
二叉树的最大深度等价于：左右子树的最大深度 + 1

代码实现：

int maxDepth(struct TreeNode* root){
    if(root==NULL)
        return 0;
    int leftdeep = maxDepth(root->left);
    int rightdeep = maxDepth(root->right);
    return (leftdeep > rightdeep)?(leftdeep+1):(rightdeep+1);
}

图例解析：
在这里插入图片描述

检查两颗树是否相同

题目链接：OJ链接
在这里插入图片描述在这里插入图片描述

提示：

两棵树上的节点数目都在范围 [0, 100] 内
-104 <= Node.val <= 104

思路解析
首先比较根节点是否相同，然后分别比较左右子树是否相同
代码实现：

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

图例解析
在这里插入图片描述

.翻转二叉树

题目链接：OJ链接
在这里插入图片描述在这里插入图片描述

提示：

树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100

思路解析
用后序翻转每一棵树的左右子树根节点
代码实现：

struct TreeNode* invertTree(struct TreeNode* root){
    if(root==NULL) return NULL;
    struct TreeNode* left=invertTree(root->left);
    struct TreeNode* right=invertTree(root->right);
    root->right=left;
    root->left=right;
    return root;
}

图例解析
在这里插入图片描述

在这里插入图片描述

对称二叉树

题目链接：OJ链接
在这里插入图片描述在这里插入图片描述

提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

思路解析
判断一个树是否对称，首先要判断左右孩子是否对称相等，还需要判断左孩子的左子树是否和右孩子的右子树对称，左孩子的右子树是否和右孩子的左子树对称。
将左右子树传入判断二叉树是否相同的函数
代码实现：

bool check(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 check(p->left, q->right) && check(p->right, q->left);
    else
        return false;
}

bool isSymmetric(struct TreeNode* root){
    return check(root, root);
}

图例解析
具体参考前面判断二叉树是否相同的例题

另一颗树的子树

题目链接：OJ链接
在这里插入图片描述在这里插入图片描述在这里插入图片描述

提示：

root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-104 <= root.val <= 104
-104 <= subRoot.val <= 104

思路解析
判断t是否为s的子树，需要判断t是否和s的某一个子树相同，所以此题就是判断两棵树是否相同的逻辑。
前序遍历到与第二棵树根节点val相同的结点
再传入比较函数进行判断
代码实现：

bool check(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 check(p->left,q->left)&&check(p->right,q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(subRoot==NULL)
        return true;
    if(root==NULL&&subRoot==NULL)
        return true;
    if(root==NULL)
        return false;
    if(root->val==subRoot->val){
        int Jb=check(root,subRoot);
        if(Jb==true)
            return true;
    }
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

图例解析
具体参考前面判断二叉树是否相同的例题及前序遍历例题

总结

现在我们开始一轮新的自我提升吧！
二叉树的题目当然也更有难度！
但没关系，一起加油，这些都是小困难！芜湖~

更多推荐

掌握ls命令：完整指南、高级用法与常见问题解答 | 理解文件管理的关键工具

文章目录引言1.1关于ls命令1.2ls命令的作用和用途ls命令的基本用法2.1命令格式和语法2.2列出当前目录内容2.3列出指定目录内容常用选项和参数3.1列出详细信息3.2列出隐藏文件3.3按不同方式排序3.4显示文件大小3.5递归列出子目录内容文件类型和权限4.1文件类型的表示4.2权限的表示和解读4.3更改文件

Java基于微信小程序的青少年健康心理科普平台

第一章简介青少年心理健康科普平台为用户提供心理医生咨询服务，系统包括微信小程序端和后台。微信小程序用户可以先进行注册，填写个人的基本信息提交到服务器，服务器把数据保存到数据库。管理员对青少年的信息进行验证后，青少年通过验证后的用户名和密码进行登录，登录之后查看健康知识。心理医生在首页展示，查看心理医生具体信息后，可以进

贪心算法的思路和典型例题

一、贪心算法的思想贪心算法是一种求解问题时，总是做出在当前看来是最好的选择，不从整体最优上加以考虑的算法。二.用贪心算法的解题策略其基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。贪心算法的关键在于贪心策略的选择，而不是对所有问题都能得到整体最优解。若下一个数据和部分

Django实现音乐网站 ⒅

使用PythonDjango框架做一个音乐网站，本篇主要为歌单列表、歌单详情及推荐页-歌单内容改动。目录歌单列表设置路由视图处理模板渲染歌单-单曲列表设置路由视图处理模板渲染推荐页-歌单列表模板渲染修改总结歌单列表可通过导航>歌单或者推荐歌单中分类跳转到歌单列表。设置路由path('songsheet',views.s

多台群晖实现按计划WOL网络自动唤醒数据冷备份

几年前买了2盘位的DS218+，但是随着照片的增加已经不够用。年中购入了4盘位的群晖DS923+、2块16T西数数企业级硬盘、1块2Tintel企业级SSD1.什么是冷备份冷备是离线备份，备份好的数据可以单独存取，定期冷备可以保证数据安全，适合家庭场景2.为什么不用Raid1Raid不是一个备份方案，Raid1是做1:

matlab GPR高斯过程回归与股票价格预测

1、回归回归分析是统计分析领域的重要分支。利用回归分析模型可以进行预测。一个典型的预测问题是：给定自变量xxx的某些值处对因变量的一些噪声观测值，对新值x∗x^*x∗时因变量的最佳估计值是多少？如果我们期望底层函数是线性的，且可以对输入数据做一些规范化假设，那么我们可以使用最小二乘法来线性回归（直线拟合）。对于一些规律

【DevOps核心理念基础】3. 敏捷开发最佳实践

一、敏捷开发最佳实践1.1项目管理1.2需求管理1.3技术架构1.4技术开发1.5测试二、敏捷开发最佳实践2.1敏捷开发的执行细节三、全面的DevOps工具链四、版本控制和协作开发工具4.1集中式版本控制工具4.2分布式版本控制工具一、敏捷开发最佳实践1.1项目管理迭代开发技术团队的人员素质，人员配备完整及时有效的沟通

解锁前端Vue3宝藏级资料 第五章 Vue 组件应用 2 ( Emit )

本章带领大家理解组件、props、emits、slots、providers/injects，Vue插件等Vue组件使用的基础知识。第一章Vue3项目创建1VueCLI创建vue项目第一章Vue3项目创建2使用Webpack5搭建vue项目第一章Vue3项目创建3Vite创建vue项目第二章Vue3基础语法指令第三章V

内存利用：迟来的blindless与逃不掉的exit漏洞

0x01前言在计算机安全领域，漏洞的危险性往往与其广泛性和潜在攻击方式密切相关。今天，我们将深入探讨一个异常危险的漏洞，它存在于程序退出时执行的常见函数"exit"中。无论是在操作系统还是应用程序中，"exit"都是一个普遍存在的函数，通常用于正常退出程序。但这种普遍性也使得它成为了潜在的攻击目标。这个漏洞的威胁性在于

华为云云耀云服务器L实例评测｜使用docker部署禅道系统

大家好，我是早九晚十二，目前是做运维相关的工作。写博客是为了积累，希望大家一起进步！我的主页：早九晚十二文章目录前言准备工作华为云账号注册充值、购买服务器服务器操作密码修改登录远程工具禅道部署简介部署安装docker设置开机自启禅道镜像包获取查找并拉取镜像创建docker容器并启动开启防火墙入站策略浏览器访问IP:PO

【2023】Jenkins入门与安装

目录1.什么是Jenkins2.Jenkins安装部署3.配置Jenkins4.优化Jenkins5.插件管理5.1.联网安装5.2.hpi文件安装5.3.离线安装6.创建项目操作系统：centos7.9JAVA版本：java-11-openjdkJenkins版本：jenkins-2.401.11.什么是Jenkin

热文推荐
  1. 全能电子地图下载器3.0-下载离线地图瓦片

    前言vue项目要部署到局域网内，不使用在线地图，而是离线地图，寻求了很多的解决方案，最终决定使用离线地图瓦片+leaflet.js实现效果！正文首先需要下载正版的软件，目前我实用的是V3.0版本的，可能和之前的有部分差异化，这个也属于正常。一、下载1.有CSDN会员下载渠道：https://download.csdn.

  2. Vue入门--vue的生命周期

    一.什么是Vue二.Vue的简介官方网址特点三.前后端的分离重大问题优势4.Vue入门定义一个管理边界​编辑测试结果vue的优势​编辑测试结果5.Vue的生命周期vue的生命周期图​编辑建立一个html测试结果一.什么是VueVue是一种流行的JavaScript前端框架，用于构建用户界面。它被设计为一种渐进式框架，可

  3. CTF —— 网络安全大赛（这不比王者好玩吗？）

    前言随着大数据、人工智能的发展，人们步入了新的时代，逐渐走上科技的巅峰。\⚔科技是一把双刃剑，网络安全不容忽视，人们的隐私在大数据面前暴露无遗，账户被盗、资金损失、网络诈骗、隐私泄露，种种迹象表明，随着互联网的发展，网络安全需要引起人们的重视。\互联网安全从其本质上来讲就是互联网上的信息安全。从广义来说，凡是涉及到互联

  4. 3.2 Android eBPF程序类型

    写在前面为什么要先了解eBPF程序类型？从帮助函数中，我们可能基于内核的eBPF开放API，对eBPF的能力有一个比较细致的认识，但是这并不能让我们从全局，或者更概括的认识eBPF。eBPF程序类型能够更宏观的告诉我们，eBPF能做哪些事情（除网络相关）。一，eBPF程序类型内核中不同事件会触发不同类型的eBPF程序，

  5. 什么是Webpack的Tree Shaking？它的作用是什么？

    聚沙成塔·每天进步一点点⭐专栏简介⭐Webpack的TreeShaking⭐作用和原理⭐使用TreeShaking⭐写在最后⭐专栏简介前端入门之旅：探索Web开发的奇妙世界欢迎来到前端入门之旅！感兴趣的可以订阅本专栏哦！这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域的朋友们量身打造的。无论你是完全的新手还是有一些

  6. 简单 php结合WebUploader实现文件上传功能

    WebUploader资源下载http://fex.baidu.com/webuploader/download.htmlWebUploader使用方法http://fex.baidu.com/webuploader/getting-started.htmlphp上传代码<?phpheader('Content-typ

  7. MFC主框架和视类PreCreateWindow()函数学习

    在VC++生成的单文档应用程序中，主框架类和视类均具有PreCreateWindow函数；从名字可知，可在此函数中添加一些代码，来控制窗口显示后的效果；并且它有注释说明，ModifytheWindowclassorstylesherebymodifyingtheCREATESTRUCTcs在这里通过修改CREATEST

  8. ​Qt for Python 入门¶​

    本页重点介绍如何从源代码构建QtforPython，如果你只想安装PySide2。与你需要运行：pippipinstallpyside2有关更多详细信息，请参阅我们的快速入门指南。此外，您可以查看与项目相关的常见问题解答。一般要求¶Python：3.5+和2.7Qt：建议使用5.12+libclang：libclang

  9. Leetcode.486 预测赢家

    题目链接Leetcode.486预测赢家mid题目描述给你一个整数数组nums。玩家111和玩家222基于这个数组设计了一个游戏。玩家111和玩家222轮流进行自己的回合，玩家111先手。开始时，两个玩家的初始分值都是000。每一回合，玩家从数组的任意一端取一个数字（即，nums[0]nums[0]nums[0]或nu