本篇文章我们依然讲解链式二叉树的OJ题；

一、二叉树的层序遍历

层序遍历即从根节点开始一层一层的遍历。我们可以运用队列的先进先出特性实现！

//层序遍历
void a(BTNode* root)
{Que qhead;Queueinit(&qhead);//先入队根节点if(root)QueuePush(&qhead, root);while (!QueueEmpty(&qhead)){BTNode* tmp = QueueFront(&qhead);printf("%d ", tmp->val);if (tmp->left != NULL){QueuePush(&qhead, tmp->left);}if (tmp->right != NULL){QueuePush(&qhead, tmp->right);}QueuePop(&qhead);}QueueDestroy(&qhead);
}

①：由代码可知，我们先初始化一个队列，然后将根节点入队，这里队列的每个结点类型都为树的指针（即树的结点）；

②：用while循环对队列进行遍历，其中注意在打印完队头数据后，我们需要判断队头的左右子树是否为NULL，若不为空，则分别将左右子树入队；

③最后出队，找到下一个树的结点；

二、判断一颗树是不是二叉树

想要判断一颗树是不是二叉树，我们就要找找二叉树的特点，当我们画出一颗二叉树观察可以知道，当一颗二叉树通过层次遍历得到的顺序中，非空结点是连续的；

所以我们有如下规律：

①：通过层次遍历，若非空节点是连续的，则是二叉树；

②：通过层次遍历，若非空节点不连续，则不是二叉树；

代码实现如下：

//判断一颗树是不是二叉树
int TreeComplete(BTNode* root)
{Que qhead;Queueinit(&qhead);//先入队根节点if (root)QueuePush(&qhead, root);//根据层序遍历思路入队，遇到NULL，则停止入队while (!QueueEmpty(&qhead)){BTNode* tmp = QueueFront(&qhead);if (tmp == NULL)break;QueuePush(&qhead, tmp->left);QueuePush(&qhead, tmp->right);QueuePop(&qhead);}//看队列的后面还有没有非空节点，若有的话，则不是二叉树while (!QueueEmpty(&qhead)){BTNode* tmp = QueueFront(&qhead);QueuePop(&qhead);if (tmp != NULL){QueueDestroy(&qhead);return 0;}/*QueuePush(&qhead, tmp->left);QueuePush(&qhead, tmp->right);*/}return 1;QueueDestroy(&qhead);
}

①：由代码可知，层次遍历的思路和第一题一样，只是因为我们要通过非空节点是否连续来判断，所以此时遇到左右孩子为NULL时，也要将其入队；

②：当第一次遍历到队头为NULL时，则停止入队；然后又遍历剩余的队列，看是否存在非空节点，若存在，则不是二叉树，返回0；若不存在，则是二叉树，返回1；

三、LeetCode——判断一颗树是不是另一颗树的子树

（一）、题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

（二）、解答

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(root->val==subRoot->val){if (isSameTree(root,subRoot))return true;}return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);}

①，要判断子树，很显然要用到判断树是否相同的原理，所以我们将之前写的“判断树相同”的的代码直接搬运过来；

②：题目规定子树subRoot不可能为NULL，所以我们先判断大树root是否为NULL，若为NULL，则直接返回false；

③：然后我们知道，只有根节点的值相等，这两棵树才有可能相同，所以先判断结点的值，若找到两个相等的结点，则调用“判断树是否相同”函数进行判断，若相等则返回true，代表是子树；若不相等，则大树继续向下找（先找左子树，然后找右子树）；

四、LeetCode——反转二叉树

（一）、题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

（二）、解答

//手写函数
void _invertTree(struct TreeNode* root1,struct TreeNode* root2)
{//为NULL则返回if(root1==NULL||root2==NULL)return ;//交换根节点int tmp = root1->val;root1->val = root2->val;root2->val = tmp;//找子树_invertTree(root1->left,root2->right);_invertTree(root1->right,root2->left);}//题目给定函数
struct TreeNode* invertTree(struct TreeNode* root) {if(root)_invertTree(root->left,root->right);return root;
}

①：根据题意，我们可以把一棵树root分为两棵树root1和root2，并且由图可以看到，只需要将两棵树的根节点的值进行交换，然后root1递归到其右子树的同时root2递归到其左子树；root1递归到其左子树的同时，root2递归到其右子树，接着依次交换顺序即可，直到最后都为NULL则返回；

五、LeetCode——判断一棵树是不是对称二叉树（镜像对称）

（一）、题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

（二）、解答

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 _isSymmetric(root->left,root->right);
}

①：思路也是参考上面几道体，既然要判断是不是镜像对称，我们就可以将一颗大树对半分成两棵树，然后观察图片可知，root1的右子树要等于root2的左子树；root1的左子树要等于root2的右子树，所以将根节点比较完后就可以给出相应递归。

本次知识到此结束，希望对你有所帮助！