赞
踩
一、之前写了二叉树的三种遍历方法:有先序遍历、中序遍历、后序遍历,这三种方法都是用递归的方式来遍历二叉树的。层序遍历则不是使用递归来遍历,而是使用队列的来实现遍历:
void LevelTreeOrder(BTNode* root) { Queue q; QueueInit(&q); if(root) QUueuePush(&q,root); while(!EmptyQueue(&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); }
代码就是如上所示,前提是你要有一个写好的队列的代码。
二、我们可以使用层序遍历来判断完全二叉树
借助于上面的写好的层序遍历,我们可以写出
void isTreeComplete(BTNode* root) { Queue q; QueueInit(&q); if(root) QUueuePush(&q,root); while(!EmptyQueue(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); if(front==NULL) break; else{ QueuePush(front->left); QueuePush(front->right); } } while(!EmptyQueue(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); if(front){ QueueDestroy(&q); return false;} } QueueDestroy(&q); return true; }
三、判断所给的树是不是对称的树
题目要求给你一棵树,需要你判断是不是一颗对称的树:
- bool _isSymmetric(struct TreeNode* root1,struct TreeNode* root2){
- if(root1 == NULL &&root2==NULL)
- return true;
- if(root1 == NULL || root2 ==NULL )
- return false;
- if(root1->val != root2->val)
- return false;
- return _isSymmetric(root1->left,root2->right)&&_isSymmetric(root1->right,root2->left);
- }
- bool isSymmetric(struct TreeNode* root){
- return !root || _isSymmetric(root->left,root->right);
- }
和之前写的isSameTree的思路还是很像的;
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。