二叉树经典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);
}

相关内容

热门资讯

王者定位怎么关安卓系统,轻松实... 你是不是也和我一样,对王者荣耀这款游戏爱得深沉呢?不过,有时候游戏里的设置让人头疼,比如安卓系统的王...
树莓派安卓系统流畅,打造便携式... 亲爱的读者们,你是否曾想过,将树莓派与安卓系统结合,会擦出怎样的火花呢?今天,就让我带你一起探索这个...
安卓系统智能机顶盒,引领家庭娱... 你有没有想过,家里的电视也能变得智能起来?没错,就是那个陪伴我们多年的老电视,现在也能摇身一变,成为...
安卓系统很差了吗现在,性能优劣... 最近是不是有不少朋友在讨论安卓系统的问题呢?有人说它越来越差了,也有人觉得它还是那个熟悉的“老朋友”...
安卓系统uc安装包,Andro... 你有没有发现,手机里的安卓系统越来越强大了?今天,咱们就来聊聊这个话题——安卓系统中的UC安装包。你...
安卓系统谷歌能删吗,谷歌能否删... 你有没有想过,那个一直陪伴你手机生活的安卓系统,它背后的谷歌爸爸,是不是也能被你随意删掉呢?这可不是...
安卓系统会不会更耗电,解析其功... 你有没有发现,手机用着用着,电池就有点不给力了?尤其是那些用安卓系统的手机,有时候感觉电就像流水一样...
安卓系统中无效目录,安卓系统无... 你有没有遇到过在安卓系统中,明明文件夹就在那里,但是就是找不到的情况?别急,今天就来给你揭秘安卓系统...
国产安卓机哪个系统好用,探寻最... 你有没有想过,国产安卓机哪个系统最好用呢?这可是个让人纠结的问题,毕竟每个系统都有它的特色和亮点。今...
安卓系统cpua9,引领性能与... 你有没有发现,最近你的安卓手机运行得是不是比以前顺畅多了?这可多亏了那个强大的安卓系统CPUA9啊!...
安卓系统usb驱动程序,功能、... 你有没有遇到过这种情况:手机里存了那么多宝贝照片和视频,想传输到电脑上保存,结果电脑却像个小顽皮,死...
安卓操作系统怎么关闭,轻松关闭... 手机里的安卓操作系统是不是有时候让你觉得有点儿烦呢?别急,今天就来手把手教你如何轻松关闭安卓操作系统...
追星手机壳推荐安卓系统,盘点热... 你有没有发现,现在追星族们对手机壳的热爱简直到了疯狂的地步?没错,就是那种能让你一秒变身偶像迷妹的手...
ios系统用安卓系统游戏下载软... 你有没有想过,明明是iOS系统的手机,却想玩安卓系统的游戏?这可不是什么天方夜谭,现在就有这么神奇的...
安卓高系统怎么用美化,打造专属... 亲爱的安卓用户们,你是不是也和我一样,对手机系统美化情有独钟呢?想要让你的安卓手机焕然一新,变得个性...
安卓系统怎么开夜间模式,安卓系... 亲爱的手机控们,你是不是在夜晚使用安卓手机时,眼睛感到有些不适?别担心,今天我要给你揭秘一个超级实用...
王者安卓系统用苹果人脸,一场视... 你知道吗?最近在手机圈里可是掀起了一股不小的波澜呢!那就是王者安卓系统竟然用上了苹果人脸识别技术!是...
安卓444怎么升级系统,轻松迈... 你那安卓444的小家伙是不是已经有点儿落伍了?别急,今天就来给你详细说说怎么给它来个系统升级,让它焕...
安卓系统raw修图软件,探索安... 你有没有发现,手机拍照越来越方便了,但有时候拍出来的照片还是不够完美呢?别急,今天就来给你安利几款安...
安卓系统的王者切换苹果,从安卓... 你知道吗?最近身边的朋友圈里掀起了一股热潮,那就是安卓系统的王者们纷纷切换到苹果阵营。这可真是让人大...