首页 最新 热门 推荐

  • 首页
  • 最新
  • 热门
  • 推荐

【数据结构初阶第十七节】二叉树算法题

  • 25-03-07 23:41
  • 3727
  • 11586
blog.csdn.net

Hi!

必须有为成功付出代价的决心,然后想办法付出这个代价。云边有个稻草人-CSDN博客 

目录

一、单值二叉树

二、相同的树

三、对称二叉树

四、另一棵树的子树

五、二叉树遍历

(1)前序遍历

(2)中序遍历

(3)后序遍历

六、二叉树的构建及遍历

七、二叉树选择题

Relaxing Time——

             —————————————— 《 像极了 》 ——————————————


正文开始——接受挑战!

一、单值二叉树

965. 单值二叉树 - 力扣(LeetCode)

【图解】 

【思路】

就是从根节点开始不断遍历,先遍历左子树,遍历到一个节点的时候判断该节点的左节点是否和该结点的值相等,再判断该节点的右节点是否和该结点相等,就这样不断地递归,return,注意,我们使用递归一定要注意递归结束的条件,本题递归结束的条件是root == NULL时结束。下面是代码+注释,照着代码把递归过程顺一遍,用箭头来代表函数栈帧的创建与销毁就没那么抽象了。把上节学的递归搞熟悉之后理解本题的递归就不是大问题。下一题—— 

【代码】 

  1. /**
  2. * Definition for a binary tree node.
  3. * struct TreeNode {
  4. * int val;
  5. * struct TreeNode *left;
  6. * struct TreeNode *right;
  7. * };
  8. */
  9. typedef struct TreeNode TreeNode;
  10. bool isUnivalTree(struct TreeNode* root)
  11. {
  12. //递归结束的条件(找递归结束的条件还是很重要的)
  13. if(root == NULL)
  14. {
  15. return true;//直接return,root == NULL不影响结果,直接返回
  16. }
  17. //先判断root的左节点是否和根节点值相同,这里是不相同直接return false(注意这里的用法)
  18. if(root->left && root->left->val != root->val)
  19. {
  20. return false;
  21. }
  22. //再判断右节点是否和根节点相同,和上面同样的道理
  23. if(root->right && root->right->val != root->val)
  24. {
  25. return false;
  26. }
  27. //紧接着递归,判断root->left和root->right,也就是root的左右子树
  28. return isUnivalTree(root->left) && isUnivalTree(root->right);
  29. }

二、相同的树

100. 相同的树 - 力扣(LeetCode)

【图解】 

【代码】

  1. /**
  2. * Definition for a binary tree node.
  3. * struct TreeNode {
  4. * int val;
  5. * struct TreeNode *left;
  6. * struct TreeNode *right;
  7. * };
  8. */
  9. typedef struct TreeNode TreeNode;
  10. bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
  11. //当两个节点都为NULL时,相等
  12. if(p == NULL && q == NULL)
  13. {
  14. return true;
  15. }
  16. //当两个节点其一为NULL,不相等
  17. if(p == NULL || q == NULL)
  18. {
  19. return false;
  20. }
  21. //两个节点都不为NULL,这时判断不相等才能说明问题
  22. if(p->val != q->val)
  23. {
  24. return false;//这是根节点不相同时
  25. }
  26. //注意这里是&&,必须左右节点都相等返回True时才可以判断相等
  27. return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
  28. }

三、对称二叉树

101. 对称二叉树 - 力扣(LeetCode)

本题会借助上题的思路,看看自己能不能做出来

【图解】

【代码】 

  1. /**
  2. * Definition for a binary tree node.
  3. * struct TreeNode {
  4. * int val;
  5. * struct TreeNode *left;
  6. * struct TreeNode *right;
  7. * };
  8. */
  9. bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
  10. //当两个节点都为NULL时,相等
  11. if(p == NULL && q == NULL)
  12. {
  13. return true;
  14. }
  15. //当两个节点其一为NULL,不相等
  16. if(p == NULL || q == NULL)
  17. {
  18. return false;
  19. }
  20. //两个节点都不为NULL,这时判断不相等才能说明问题
  21. if(p->val != q->val)
  22. {
  23. return false;//这是根节点不相同时
  24. }
  25. //这里判断节点是否相同,注意传参的内容
  26. return isSameTree(p->left,q->right) && isSameTree(p->right,q->left);
  27. }
  28. bool isSymmetric(struct TreeNode* root)
  29. {
  30. //调用上面的判断树是否相等的函数,注意这里传的形参,返回判断树是否相同的结果true/false
  31. return isSameTree(root->left,root->right);
  32. }

四、另一棵树的子树

572. 另一棵树的子树 - 力扣(LeetCode)

【图解】

【代码】 

  1. /**
  2. * Definition for a binary tree node.
  3. * struct TreeNode {
  4. * int val;
  5. * struct TreeNode *left;
  6. * struct TreeNode *right;
  7. * };
  8. */
  9. bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
  10. //当两个节点都为NULL时,相等
  11. if(p == NULL && q == NULL)
  12. {
  13. return true;
  14. }
  15. //当两个节点其一为NULL,不相等
  16. if(p == NULL || q == NULL)
  17. {
  18. return false;
  19. }
  20. //两个节点都不为NULL,这时判断不相等才能说明问题
  21. if(p->val != q->val)
  22. {
  23. return false;//这是根节点不相同时
  24. }
  25. return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
  26. }
  27. bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
  28. {
  29. if(root == NULL)
  30. {
  31. return false;
  32. }
  33. //从根节点判断树是否相等
  34. if(isSameTree(root,subRoot))
  35. {
  36. return true;
  37. }
  38. //再去递归root树的左子树,判断与subRoot是否相等
  39. return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
  40. }

五、二叉树遍历

(1)前序遍历

144. 二叉树的前序遍历 - 力扣(LeetCode)

【图解】

【代码】 

  1. /**
  2. * Definition for a binary tree node.
  3. * struct TreeNode {
  4. * int val;
  5. * struct TreeNode *left;
  6. * struct TreeNode *right;
  7. * };
  8. */
  9. /**
  10. * Note: The returned array must be malloced, assume caller calls free().
  11. */
  12. typedef struct TreeNode TreeNode;
  13. int TreeSize(TreeNode* root)
  14. {
  15. //总的节点个数 = 根节点1 + 左子树结点个数 + 右子树结点个数
  16. if(root == NULL)
  17. {
  18. return 0;
  19. }
  20. return 1 + TreeSize(root->left) + TreeSize(root->right);
  21. }
  22. void _preorderTraversal(TreeNode* root,int* arr,int* pi)
  23. {
  24. //前序遍历 根 左 右
  25. if(root == NULL)
  26. {
  27. return;
  28. }
  29. arr[(*pi)++] = root->val;
  30. _preorderTraversal(root->left,arr,pi);
  31. _preorderTraversal(root->right,arr,pi);
  32. }
  33. int* preorderTraversal(struct TreeNode* root, int* returnSize) {
  34. //我们要将树遍历的结果放到数组里面,所以我们要动态创建一个数组
  35. //1.获取树的结点的个数,为动态开辟数组内存空间做准备
  36. *returnSize = TreeSize(root);
  37. //2.动态开辟一块空间
  38. int* returnArr = (int*)malloc(sizeof(int)*(*returnSize));
  39. //3.前序遍历树并存入到数组里面
  40. int i = 0;
  41. _preorderTraversal(root,returnArr,&i);
  42. return returnArr;
  43. }

(2)中序遍历

94. 二叉树的中序遍历 - 力扣(LeetCode)

中序遍历和前序遍历对于这道题来说其实都是一样的,只是其中遍历的方式不一样,整体思路是一样的,后序遍历亦是如此,前面的前、中、后序遍历学得OK的话实现这两道就没有任何问题。

【代码】

  1. /**
  2. * Definition for a binary tree node.
  3. * struct TreeNode {
  4. * int val;
  5. * struct TreeNode *left;
  6. * struct TreeNode *right;
  7. * };
  8. */
  9. /**
  10. * Note: The returned array must be malloced, assume caller calls free().
  11. */
  12. typedef struct TreeNode TreeNode;
  13. int TreeSize(TreeNode* root)
  14. {
  15. //总的节点个数 = 根节点1 + 左子树结点个数 + 右子树结点个数
  16. if(root == NULL)
  17. {
  18. return 0;
  19. }
  20. return 1 + TreeSize(root->left) + TreeSize(root->right);
  21. }
  22. void _inorderTraversal(TreeNode* root,int* arr,int* pi)
  23. {
  24. //中序遍历 左 根 右
  25. if(root == NULL)
  26. {
  27. return;
  28. }
  29. _inorderTraversal(root->left,arr,pi);
  30. arr[(*pi)++] = root->val;
  31. _inorderTraversal(root->right,arr,pi);
  32. }
  33. int* inorderTraversal(struct TreeNode* root, int* returnSize) {
  34. //我们要将树遍历的结果放到数组里面,所以我们要动态创建一个数组
  35. //1.获取树的结点的个数,为动态开辟数组内存空间做准备
  36. *returnSize = TreeSize(root);
  37. //2.动态开辟一块空间
  38. int* returnArr = (int*)malloc(sizeof(int)*(*returnSize));
  39. //3.前序遍历树并存入到数组里面
  40. int i = 0;
  41. _inorderTraversal(root,returnArr,&i);
  42. return returnArr;
  43. }

(3)后序遍历

145. 二叉树的后序遍历 - 力扣(LeetCode)

【代码】

  1. /**
  2. * Definition for a binary tree node.
  3. * struct TreeNode {
  4. * int val;
  5. * struct TreeNode *left;
  6. * struct TreeNode *right;
  7. * };
  8. */
  9. /**
  10. * Note: The returned array must be malloced, assume caller calls free().
  11. */
  12. typedef struct TreeNode TreeNode;
  13. int TreeSize(TreeNode* root)
  14. {
  15. //总的节点个数 = 根节点1 + 左子树结点个数 + 右子树结点个数
  16. if(root == NULL)
  17. {
  18. return 0;
  19. }
  20. return 1 + TreeSize(root->left) + TreeSize(root->right);
  21. }
  22. void _postorderTraversal(TreeNode* root,int* arr,int* pi)
  23. {
  24. //中序遍历 左 根 右
  25. if(root == NULL)
  26. {
  27. return;
  28. }
  29. _postorderTraversal(root->left,arr,pi);
  30. _postorderTraversal(root->right,arr,pi);
  31. arr[(*pi)++] = root->val;
  32. }
  33. int* postorderTraversal(struct TreeNode* root, int* returnSize) {
  34. //我们要将树遍历的结果放到数组里面,所以我们要动态创建一个数组
  35. //1.获取树的结点的个数,为动态开辟数组内存空间做准备
  36. *returnSize = TreeSize(root);
  37. //2.动态开辟一块空间
  38. int* returnArr = (int*)malloc(sizeof(int)*(*returnSize));
  39. //3.前序遍历树并存入到数组里面
  40. int i = 0;
  41. _postorderTraversal(root,returnArr,&i);
  42. return returnArr;
  43. }

六、二叉树的构建及遍历

二叉树遍历_牛客题霸_牛客网

其实这道题整体不是很难,代码里面用到的申请结点,中序遍历啥的我们前面都写过,就是思路的第二点难些需要我们自己写一个二叉树递归的创建。

这是牛客网上的题,所有的都要自己实现,头文件也要自己写。

【代码】

  1. #include
  2. #include
  3. typedef struct BinaryTreeNode
  4. {
  5. char data;
  6. struct BinaryTreeNode* left;
  7. struct BinaryTreeNode* right;
  8. }BTNode;
  9. BTNode* buyNode(char x)
  10. {
  11. BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
  12. newnode->data = x;
  13. newnode->left = newnode->right = NULL;
  14. return newnode;
  15. }
  16. BTNode* createTree(char* arr,int* pi)
  17. {
  18. //递归结束的条件
  19. if(arr[(*pi)] == '#')
  20. {
  21. (*pi)++;
  22. return NULL;
  23. }
  24. BTNode* root = buyNode(arr[(*pi)++]);
  25. root->left = createTree(arr,pi);
  26. root->right = createTree(arr,pi);
  27. return root;
  28. }
  29. //中序遍历
  30. void InOrder(BTNode* root)
  31. {
  32. if(root == NULL)
  33. {
  34. return;
  35. }
  36. InOrder(root->left);
  37. printf("%c ",root->data);
  38. InOrder(root->right);
  39. }
  40. int main()
  41. {
  42. //1.读取用户的输入并存入到数组里面
  43. char arr[100];
  44. scanf("%s",arr);
  45. //2.根据前序遍历字符串创建二叉树
  46. int i = 0;
  47. BTNode* root = createTree(arr,&i);
  48. //3.中序遍历二叉树
  49. InOrder(root);
  50. return 0;
  51. }

好了,到这里OJ题就告一段落了,下面开展选择题——

七、二叉树选择题

我们要先学习二叉树的一个性质

(1)对任何⼀棵⼆叉树, 如果度为 0 其叶结点个数为 n 0 , 度为 2 的分⽀结点个数为 n 2 ,则有 n 0 = n 2 + 1

学完这个性质我们来练练选择题,我们先独立做一下,题目后面有答案+解析

 【解析】

链式二叉树遍历选择题

【解析】 

本篇关于链式二叉树的习题就结束了,课下要多思考多自己实现代码多实践!

别害怕,即使很难也要前进,只不过是速度慢一点,也总比原地踏步的好,你觉得难,别人自然也不会觉得简单,别人都能学,我们为什么要退缩呢?前面一节我学习二叉链里面的递归一开始也觉得挺难的,但是我们可以尝试把它当做一块硬骨头,虽然难,但是我们一点一点的啃,一点一点的攻破,多整体思考几次也就觉得没那么难了,甚至自己都会写了。既然选择了这条路我就要坚定地走下去!

依旧是认真地完成了本节课的博客,下节课学习排序。。。

完——


Relaxing Time——

跟你分享一首歌吧

             —————————————— 《 像极了 》 ——————————————

像极了_永彬Ryan.B_高音质在线试听_像极了歌词|歌曲下载_酷狗音乐

至此结束——

我是云边有个稻草人

期待与你的下一次相遇。。。拜~~~

注:本文转载自blog.csdn.net的云边有个稻草人的文章"https://blog.csdn.net/lrq13965748542/article/details/145890782"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接
复制链接
相关推荐
发表评论
登录后才能发表评论和回复 注册

/ 登录

评论记录:

未查询到任何数据!
回复评论:

分类栏目

后端 (14832) 前端 (14280) 移动开发 (3760) 编程语言 (3851) Java (3904) Python (3298) 人工智能 (10119) AIGC (2810) 大数据 (3499) 数据库 (3945) 数据结构与算法 (3757) 音视频 (2669) 云原生 (3145) 云平台 (2965) 前沿技术 (2993) 开源 (2160) 小程序 (2860) 运维 (2533) 服务器 (2698) 操作系统 (2325) 硬件开发 (2492) 嵌入式 (2955) 微软技术 (2769) 软件工程 (2056) 测试 (2865) 网络空间安全 (2948) 网络与通信 (2797) 用户体验设计 (2592) 学习和成长 (2593) 搜索 (2744) 开发工具 (7108) 游戏 (2829) HarmonyOS (2935) 区块链 (2782) 数学 (3112) 3C硬件 (2759) 资讯 (2909) Android (4709) iOS (1850) 代码人生 (3043) 阅读 (2841)

热门文章

113
数据结构与算法
关于我们 隐私政策 免责声明 联系我们
Copyright © 2020-2025 蚁人论坛 (iYenn.com) All Rights Reserved.
Scroll to Top