二叉树顶上战争实战——手撕数据结构

举报
乔乔家的龙龙 发表于 2022/04/15 09:18:19 2022/04/15
【摘要】 带你一命通关二叉树 五分钟手撕经典OJ 从此单手吊打数据结构

@TOC

传统艺能😎

小编是双非本科大一菜鸟不赘述,欢迎大佬指点江山(QQ:1319365055)
此前博客点我!点我!请搜索博主 【知晓天空之蓝】

倾力打造转码社区微信公众号,等你加入:
在这里插入图片描述

1.二叉树最大深度🤔

链接:二叉树最大深度

给定一个二叉树,找出其最大深度,二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

示例:
给定二叉树 [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7

返回它的最大深度 3 。

==思路==: 从现在开始,给我记住谈到二叉树必须敏感俩个字: 递归!!

没错,很多二叉树的OJ题会把递归的思想体现的淋漓尽致,因为 Tree 的构成是利用递归去实现和定义的。

DFS🤔

最大深度就是指最长路径的结点数,那问题就来到了如何确定最长路径,这里就要引入一个思想叫: DFS,即深度优先搜索。

和他类似的还有广度优先搜索,也是对一个连通图进行遍历的算法。==它的思想是从一个顶点V0开始,沿着一条路一直走到底,如果发现不能到达目标解,那就返回到上一个节点,然后从另一条路开始走到底,这种尽量往深处走的概念即是深度优先的概念==。

这个场景下 DFS 含义并不难理解,但我们需要知道如何去实现他。

分治思想(法)🤔

我们很明确的一点就是二叉树的结构一共只有三个部分:根节点,左子树,右子树;不管是二叉树还是他的子树还是他的子树的子树,这个结构是雷打不动的,那么我们要统计一棵树上的要素,我们就可以让他们各司其职,这就引入了分治法这个概念
在这里插入图片描述
==分治法含义就是将一个大的问题分解成若干个小的问题,并且这些小问题与大问题的问题性质保持一致,通过处理小问题从而处理大问题==,这里又用到了递归的思想哈。

我们把二叉树硬掰成 “左子树+右子树” 结构,就好像皇上今天想算 1+1 ,但他就是懒,让我宰相和太尉来算,而两人也是懒狗,宰相交给他下面的尚书,太尉交给他下面的太傅……知道没有下级才开始返回结果,这么看来我们算 1+1 就相当于是统计 宰相+太尉 两条路的答案。

实现🤔

那么要解决这道题就有三个关键点:明白 Tree 的构成,DFS思想找出深度以及考虑 root 节点为空的情况:

int maxDepth(struct TreeNode* root){
if(root==NULL)
{
    return 0;
}
int m = maxDepth(root->left);//左子树遍历
int n = maxDepth(root->right);//右子树遍历
return m>n?m+1:n+1;//返回较大的一方(不要忘了加上根节点)
}

别看这简简单单几行代码,浓缩的信息量却是巨大的,大家可以画画图体会体会整个递归过程。
在这里插入图片描述

2.单值二叉树🤔

链接:单值二叉树

如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树,只有给定的树是单值二叉树时,才返回 true;否则返回 false

在这里插入图片描述

输入:[1,1,1,1,1,null,1]
输出:true

==思路==:如果上一道题摆弄明白了,这道题也就简单了,基本方法是分治法+对比判断,这里对比时注意我们判断为 true 的情况比较多,那我们可以转向去罗列 false 的情况。

bool dfs(struct TreeNode* root,int k)
{if(root == NULL)
     {
     return true;
     }//排除空树
if(dfs(root->left,k)==false)
{
    return false;//左子树节点不匹配
}
if(dfs(root->right,k)==false)
{
    return false;//右子树节点不匹配
}
if(root->val!=k)
{
    return false;//根节点节点不匹配
}
return true;
 }
bool isUnivalTree(struct TreeNode* root){
return dfs(root,root->val);//递归调用遍历Tree
}

在这里插入图片描述

引申:

我们同样可以借助分治+递归的基本模型思想解决二叉树的一些衍生的基本操作

Tree节点数🤔

同理于最大深度,不同点在于这是求和不是求最大值

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

叶子节点个数🤔

明确叶子节点结构为 左孩子和右孩子为空,满足就返回1,递归进行计数即可:

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

第K层节点数🤔

这个稍微需要思考一下,如何定位k层这个条件是题目唯一的难点,我们依然采用递归的形式去得到目标层数,在递归中增设一个条件为 (k-1),用作每次递归来逐渐接近层数,刚开始为 k 层,递归到子节点时为 (k-1),再递归到 (k-2),直到 k 为1时即证明到达了目标层:

int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
{
	return 0;
}
if (k == 1)
{
	return 1;//找到目标层所满足的K值
}
	int m = BinaryTreeLevelKSize(root->left, k - 1);
	int n = BinaryTreeLevelKSize(root->right, k - 1);
	return m + n;
}

三大遍历👏

二叉树的深度优先遍历可细分为前序遍历、中序遍历、后序遍历,这三种遍历可以用递归实现,也可使用非递归实现(主要分析递归实现)。

前序遍历🤔

前序遍历的特点为 根节点->左子树->右子树,注意看代码放入数据是放在两条递归语句之前的,所以先访问根节点 root,数据放入 root,然后访问左子树root->left,此时左子树又作为根节点放入数据,再访问此时根节点的左子树……

void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
    {
	       return;
    }
	if (root)
	{
		putchar(root->data);
		BinaryTreePrevOrder(root->left);
		BinaryTreePrevOrder(root->right);
	}
}

中序遍历🤔

中序遍历的特点为 左子树->根节点->右子树,原理和前序遍历相同,不赘述:

void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeInOrder(root->left);
	putchar(root->data);
	BinaryTreeInOrder(root->right);
}

后序遍历🤔

中序遍历的特点为 左子树->右子树->根节点,原理和前序遍历相同,不赘述:

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	putchar(root->data);
}

今天就先到这里吧,摸了家人们

【版权声明】本文为华为云社区用户原创内容,未经允许不得转载,如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。