二叉树经典14题——初学二叉树必会的简单题
创始人
2024-05-31 03:56:07
0

此篇皆为leetcode、牛客中的简单题型和二叉树基础操作,无需做过多讲解,仅付最优解。有需要的小伙伴直接私信我~

目录

1.二叉树的节点个数

2.二叉树叶子节点个数

3.二叉树第K层节点个数

4.查找值为X的节点

5.leetcode——二叉树的最大深度

6.leetcode——单值二叉树

7.leetcode——相同的树

8.二叉树的前序遍历

9.二叉树的中序遍历 

10.二叉树的后序遍历 

11.二叉树的层序遍历

12.leetcode——另一棵树的子树

13.二叉树的构建及遍历 

14.leetcode——对称二叉树


1.二叉树的节点个数

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

2.二叉树叶子节点个数

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

3.二叉树第K层节点个数

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

4.查找值为X的节点

BTNode* BinaryTreeFind(BTNode* root, BTDataType data)
{if (root == NULL)return NULL;if (root->data == data)return root;BTNode* ret1 = BinaryTreeFind(root->left, data);if (ret1)return ret1;BTNode* ret2 = BinaryTreeFind(root->right, data);if (ret2)return ret2;return NULL;
}

5.leetcode——二叉树的最大深度

oj链接:二叉树的最大深度

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

6.leetcode——单值二叉树

oj链接:单值二叉树

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

7.leetcode——相同的树

oj链接:相同的树

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

8.二叉树的前序遍历

详细讲解:二叉树的前、中、后序遍历

void PrevOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%d ", root->data);//前序在前PrevOrder(root->left);PrevOrder(root->right);
}

9.二叉树的中序遍历 

void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->data);//中序在中InOrder(root->right);
}

10.二叉树的后序遍历 

void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);//后序在后
}

11.二叉树的层序遍历

详细讲解:看完这篇我不信你不会二叉树的层序遍历

//需自己实现队列的数据结构
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);elsereturn;while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);printf("%d ", front->data);QueuePop(&q);if(front->left)QueuePush(&q, front->left);if(front->right)QueuePush(&q, front->right);}printf("\n");QueueDestroy(&q);
}

12.leetcode——另一棵树的子树

oj链接:另一棵树的子树

//判断两树是否相同(复用“相同的树”解题代码)
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);
}

13.二叉树的构建及遍历 

题目链接:二叉树的遍历

注意:本题虽然是二叉树的遍历,但考查的却是如何通过数组的内容构建一棵二叉树。

#include 
#include struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;};struct TreeNode* rebuildTree(char* str,int* pi)
{if(str[*pi] == '#'){(*pi)++;return NULL;}struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));root->val = str[(*pi)++];root->left = rebuildTree(str,pi);root->right = rebuildTree(str,pi);return root;
}void TreeDestory(struct TreeNode* root)
{if(root==NULL)return;TreeDestory(root->left);TreeDestory(root->right);free(root);
}void InOrder(struct TreeNode* 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;struct TreeNode* root = rebuildTree(str,&i);InOrder(root);TreeDestory(root);return 0;
}

14.leetcode——对称二叉树

oj链接:对称二叉树

bool _isSymmetric(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 _isSymmetric(p->left, q->right) &&_isSymmetric(p->right, q->left);
}
bool isSymmetric(struct TreeNode* root) {return root == NULL ? 0 : _isSymmetric(root->left, root->right);
}

相关内容

热门资讯

安卓系统用的华为应用,探索智能... 你知道吗?在安卓系统里,华为的应用可是个宝库呢!它们不仅功能强大,而且使用起来超级方便。今天,就让我...
安卓变ios系统魅蓝 你知道吗?最近有个朋友突然告诉我,他要把自己的安卓手机换成iOS系统,而且还是魅蓝品牌的!这可真是让...
幻书启世录安卓系统,安卓世界中... 亲爱的读者们,你是否曾在某个夜晚,被一本神奇的书所吸引,仿佛它拥有着穿越时空的力量?今天,我要带你走...
电脑安装安卓系统进不去,安卓系... 电脑安装安卓系统后竟然进不去,这可真是让人头疼的问题啊!你是不是也遇到了这种情况,心里直呼“怎么办怎...
用键盘切换控制安卓系统,畅享安... 你有没有想过,用键盘来控制你的安卓手机?是的,你没听错,就是那个我们每天敲敲打打的小玩意儿——键盘。...
小米安卓镜像系统在哪,小米安卓... 你有没有想过,你的小米手机里有一个隐藏的宝藏——安卓镜像系统?没错,就是那个可以让你的手机瞬间变身成...
安卓手机下载排班系统,高效排班... 你有没有想过,每天忙碌的工作中,有没有什么好帮手能帮你轻松管理时间呢?今天,就让我来给你介绍一个超级...
桌面组件如何弄安卓系统,桌面组... 亲爱的桌面爱好者们,你是否曾梦想过将安卓系统搬到你的电脑桌面上?想象那些流畅的动画、丰富的应用,还有...
安卓13系统介绍视频,新功能与... 亲爱的读者们,你是否对安卓13系统充满好奇?想要一探究竟,却又苦于没有足够的时间去研究?别担心,今天...
车机安卓7.1系统,功能升级与... 你有没有发现,现在的车机系统越来越智能了?尤其是那些搭载了安卓7.1系统的车机,简直就像是个贴心的智...
安卓系统下如何读pdf,And... 你有没有遇到过这种情况:手机里存了一大堆PDF文件,可是怎么也找不到一个能顺畅阅读的工具?别急,今天...
安卓系统全国通用的吗,畅享智能... 你有没有想过,为什么你的手机里装的是安卓系统呢?安卓系统,这个名字听起来是不是有点神秘?今天,就让我...
假苹果手机8安卓系统,颠覆传统... 你有没有想过,如果苹果手机突然变成了安卓系统,会是怎样的景象呢?想象那熟悉的苹果外观,却运行着安卓的...
安卓12.0系统vivo有吗,... 你有没有听说最近安卓系统又升级啦?没错,就是那个让手机焕然一新的安卓12.0系统!那么,咱们国内的手...
核心芯片和安卓系统,探索核心芯... 你知道吗?在科技的世界里,有一对“黄金搭档”正悄悄改变着我们的生活。他们就是——核心芯片和安卓系统。...
如何调安卓系统屏幕颜色,安卓系... 亲爱的手机控们,你是否曾觉得安卓系统的屏幕颜色不够个性,或者是因为长时间盯着屏幕而感到眼睛疲劳?别担...
旧台式电脑安装安卓系统,轻松安... 你那台旧台式电脑是不是已经服役多年,性能逐渐力不从心,却又不忍心让它退役呢?别急,今天就来教你怎么给...
美国要求关闭安卓系统,科技霸权... 美国要求关闭安卓系统:一场技术革新还是政治博弈?在数字化时代,智能手机已经成为我们生活中不可或缺的一...
安卓系统日记本 你有没有发现,手机里的安卓系统日记本,简直就是记录生活点滴的宝藏库呢?想象每天忙碌的生活中,有没有那...
安卓手机广告最少的系统,探索安... 你有没有发现,用安卓手机的时候,广告总是无处不在,让人烦得要命?不过别急,今天我要给你揭秘一个秘密—...