【二叉树经典习题讲解】
创始人
2024-04-27 07:21:41
0

If you find a path with no obstacles, probably doesn't lead anywhere.

目录

1 前中后序遍历一颗二叉树

2 总的结点个数

3 求叶子节点个数

4 求树的高度

5 第k层结点个数

6 二叉树的层序遍历

7 判断一棵树是否为完全二叉树


1 二叉树的前序遍历

2 单值二叉树

3 翻转二叉树

4 相同的树

5 对称二叉树

6 另一颗树的子树

7 二叉树的构建和遍历


刚开始我们来回顾练习一下比较基础的求解二叉树的一些问题:像前(中,后)序遍历一颗二叉树,求总的结点个数,求叶子结点个数,树的高度等等。

1 前中后序遍历一颗二叉树

代码实现:

void PrevOrder(BTNode* root)
{if (root == NULL){printf("NULL ");//可加可不加,加了更好理解return;}printf("%d ", root->val);PrevOrder(root->left);PrevOrder(root->right);
}void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");//可加可不加,加了更好理解return;}InOrder(root->left);printf("%d ", root->val);InOrder(root->right);
}void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");//可加可不加,加了更好理解return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->val);
}

2 总的结点个数

具体代码:

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

3 求叶子节点个数

具体代码:

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

4 求树的高度

具体代码:

int TreeHeight(BTNode* root)
{//方法1://if (root == NULL)//	return 0;//0不能省略//return TreeHeight(root->left) > TreeHeight(root->right) ? TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;//缺陷:函数递归被重复调用次数过多,效率低下,不可取//改进方法:if (root == NULL)return 0;int leftH = TreeHeight(root->left);int rightH = TreeHeight(root->right);return leftH > rightH ? leftH + 1 : rightH + 1;
}

5 第k层结点个数

具体代码:

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

6 二叉树的层序遍历

解题思路:用队列存储二叉树的根节点,pop根节点之前将不为空的孩子继续入队列,直到队列为空。

具体代码:

void TreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->val);if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}
}

7 判断一棵树是否为完全二叉树

解题思路:很显然用节点个数是无法判断出一棵树是否为完全二叉树的。判断一棵树是否为完全二叉树的最关键步骤是是否这棵树连续,比较好一种方法是利用层序遍历来处理,将根节点的孩子都入队,不管是否为空,遇到空就跳出来,然后检查后面是否有非空。

具体代码:

bool isCompleteTree(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);if (!front)break;//遇到空就跳出来QueuePop(&q);QueuePush(&q, front->left);QueuePush(&q, front->right);}//判断后面是否还有非空while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);if (front){QueueDestroy(&q);return false;}QueuePop(&q);}QueueDestroy(&q);return true;
}

接下来就是力扣或者牛客上的OJ:

1 二叉树的前序遍历

解题思路:等等,这道题不是之前讲过了吗?之前讲过是没错,不过在力扣上这道题要求你将前序遍历的结果返回到一个数组中然后返回,具体实现上要稍微麻烦一些。

具体代码:

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

2 单值二叉树

解题思路:我们知道如果当前根为空,就可以暂时认为返回结果是true(并不能确定整棵树的情况),但是只要根与左孩子或者右孩子只要有一个不相等的话就可以返回false,然后再不断递归下去,具体实现代码方式有两种,大家可以自行选择。

具体代码:

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

3 翻转二叉树

具体代码:

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

4 相同的树

具体代码:

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
if(p==NULL && q==NULL)return true;
else if(p==NULL || q==NULL)return false;
else if(p->val != q->val)return false;
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

5 对称二叉树

解题思路:有点儿类似与相同的树的解题思路,设置一个check函数帮助我们判断左右子树是否相等。

 具体代码:

bool check(struct TreeNode* p,struct TreeNode* q)
{
if(!p && !q)return true;
if(!p || !q)return false;
return p->val == q->val && check(p->left,q->right) && check(p->right,q->left);
}bool isSymmetric(struct TreeNode* root){
return check(root,root);
}

6 另一颗树的子树

解题思路:将该树的每一颗子树与要比较的树比较是否相等,若有一棵树相等,就返回true,全都不相等就返回false.

具体代码:

bool isSame(struct TreeNode* p, struct TreeNode* q)
{
if(!p && !q)return true;
if(!p || !q)return false;
if(p->val != q->val)return false;
return isSame(p->left,q->left) && isSame(p->right,q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
if(!root)return false;
if(isSame(root,subRoot))return true;
return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

7 二叉树的构建和遍历

解题思路:与在力扣上的题不同,牛客上的题大都是IO型的,所以需要我们自己输入输出,有了前面的那些例子,构建这颗二叉树也不算太难,唯一需要注意的就是构建时传入的是i的地址,因为后面数据都是要不断迭代走的。

具体代码:

#include 
#include
typedef struct BinaryTree {char val;struct BinaryTree* left;struct BinaryTree* right;
} BT;BT* PrevCreat(char* str, int* pi) {if (str[*pi] == '#') {(*pi)++;return NULL;}BT* root = (BT*)malloc(sizeof(BT));root->val = str[(*pi)++];root->left = PrevCreat(str, pi);root->right = PrevCreat(str, pi);return root;
}void InOrder (BT* root) {if (!root)return;InOrder(root->left);printf("%c ", root->val);InOrder(root->right);
}int main() {char str[101];scanf("%s", str);int i = 0;BT* root = PrevCreat(str, &i);InOrder(root);return 0;
}

相关内容

热门资讯

安卓双系统添加应用,轻松实现多... 你有没有想过,你的安卓手机里可以同时运行两个系统呢?听起来是不是很酷?想象一边是熟悉的安卓系统,一边...
pipo安卓进系统慢,探究pi... 最近是不是发现你的Pipo安卓系统更新或者运行起来特别慢?别急,今天就来给你好好分析分析这个问题,让...
怎样使用安卓手机系统,安卓手机... 你有没有发现,安卓手机已经成为我们生活中不可或缺的一部分呢?从早晨闹钟响起,到晚上睡前刷剧,安卓手机...
双系统安卓安装caj,轻松实现... 你有没有想过,你的安卓手机里装上双系统,是不是就能同时享受安卓和Windows系统的乐趣呢?没错,这...
安卓使用ios系统教程,安卓用... 你是不是也和我一样,对安卓手机上的iOS系统充满了好奇?想要体验一下苹果的优雅和流畅?别急,今天我就...
安卓系统gps快速定位,畅享便... 你有没有遇到过这样的情况:手机里装了各种地图导航软件,但每次出门前都要等上好几分钟才能定位成功,急得...
安卓手机系统更新原理,原理与流... 你有没有发现,你的安卓手机最近是不是总在提醒你更新系统呢?别急,别急,让我来给你揭秘一下安卓手机系统...
安卓系统通知管理,全面解析与优... 你有没有发现,手机里的通知就像是一群调皮的小精灵,时不时地跳出来和你互动?没错,说的就是安卓系统的通...
安卓系统手机哪买,揭秘哪里购买... 你有没有想过,拥有一部安卓系统手机是多么酷的事情呢?想象你可以自由安装各种应用,不受限制地探索各种功...
安卓系统 ipv4,基于安卓系... 你知道吗?在智能手机的世界里,有一个系统可是无人不知、无人不晓,那就是安卓系统。而在这个庞大的安卓家...
目前安卓是什么系统,探索安卓系... 亲爱的读者,你是否曾好奇过,如今安卓系统究竟是什么模样?在这个科技飞速发展的时代,操作系统如同人体的...
安卓6.0系统比5.0,从5.... 你有没有发现,自从手机更新了安卓6.0系统,感觉整个人都清爽了不少呢?没错,今天咱们就来聊聊这个话题...
安卓2.36系统升级,功能革新... 你知道吗?最近安卓系统又来了一次大变身,那就是安卓2.36系统升级!这可不是一个小打小闹的更新,而是...
安卓系统源码怎么打开,并可能需... 你有没有想过,安卓系统的源码就像是一扇神秘的门,隐藏着无数的技术秘密?想要打开这扇门,你得掌握一些小...
安卓8.0系统体验视频,智能革... 你有没有听说安卓8.0系统最近可是火得一塌糊涂啊!作为一个紧跟科技潮流的数码达人,我当然要来给你好好...
宣传系统漫画app安卓,探索安... 亲爱的读者们,你是否曾在某个午后,百无聊赖地打开手机,想要寻找一些轻松愉悦的读物?今天,我要给你介绍...
鸿蒙替换安卓系统吗,开启智能生... 你知道吗?最近科技圈里可是炸开了锅,因为华为的新操作系统鸿蒙系统,据说要大举进军手机市场,替换掉安卓...
手机安卓系统深度清理,解锁手机... 手机里的东西是不是越来越多,感觉就像一个装满了杂物的储物柜?别急,今天就来教你一招——手机安卓系统深...
安卓上的windows系统,融... 你有没有想过,在安卓手机上也能体验到Windows系统的魅力呢?没错,这就是今天我要跟你分享的神奇故...
安卓系统焦点变化事件,Andr... 你知道吗?在安卓系统的世界里,最近发生了一件超级有趣的事情——焦点变化事件。这可不是什么小打小闹,它...