前言：
通过前面的学习，我们已经学习了二叉树的基础知识，以及二叉树功能的实现。我们学习讲究的是：知行合一。那我们一起来检验一下我们的学习成果吧！
一、单值二叉树
题目描述：
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回
true；否则返回false。
思路分析：
单值二叉树就是二叉树每个节点的值都相同，这时，我们有两种思路去实现：
方法一：再构造一个函数，把根节点的值传过去和左节点和右节点进行比较，如果相同，这个没啥意义，应用不同来判断，如果不同就返回假，为真就继续递归。
方法二：用根节点和其左右节点进行比较，思路与上文类似。
本题采用方法二。
代码实现：
1. bool isUnivalTree(struct TreeNode* root) { 2. if(root == NULL) 3. { 4. return true; 5. } 6. if(root->left && root->val != root->left->val || root->right && root->right->val != root->val) 7. { 8. return false; 9. } 10. return isUnivalTree(root->left) && isUnivalTree(root->right); 11. }
以下是递归展开图，大致展示了函数调用过程，帮助大家理解： 
题目链接：. - 力扣（LeetCode）
二、二叉树最大深度
题目描述：
给定一个二叉树
root，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
思路分析：
此题一看不是和之前讲解的高度一样吗？对于我之前的说明不以为然的读者，可能会写出以下代码：
1. int maxDepth(struct TreeNode* root) { 2. if(root == NULL) 3. { 4. return 0; 5. } 6. return maxDepth(root->left) > maxDepth(root->right) ? maxDepth(root->left)+1:maxDepth(root->right)+1; 7. }
这段代码运行的大逻辑是没错的，但是会有效率问题，测试用例通过是没啥问题的，但要是要求时间复杂度了，就危险了。 
可以看出，超出了时间限制，这时我们就要对其进行优化，具体过程上一篇文章已经分析过了，优化方法为：加一个记录的变量即可，便可减少复杂度。
代码实现：
1. int maxDepth(struct TreeNode* root) { 2. if(root == NULL) 3. { 4. return 0; 5. } 6. int left = maxDepth(root->left); 7. int right = maxDepth(root->right); 8. return left > right ? left+1:right+1; 9. }
题目链接：. - 力扣（LeetCode）
三、检查两颗树是否相同
题目描述：
给你两棵二叉树的根节点
p和q，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
思路分析：
本题要求判断两颗树是否相同，那么，这么说明两颗树相同呢？无外乎就是一一比较，根与根比较，左子树与左子树比较，右子树与右子树比较，就这么简单。但，我们还要考虑的情况是：如果为空，这么判断，分两种情况：一、都为空：那就返回true。二、一个为空，另一个不为空。该放回false。以上便是所有情况。
代码实现：
1. bool isSameTree(struct TreeNode* p, struct TreeNode* q) { 2. if(p == NULL && q == NULL) 3. { 4. return true; 5. } 6. if(p == NULL || q == NULL)//此代码用来判断情况二，非常巧妙 7. { 8. return false; 9. } 10. if(p->val != q->val) 11. { 12. return false; 13. } 14. return isSameTree(p->left,q->left) && isSameTree(p->right,q->right); 15. }
题目链接：. - 力扣（LeetCode）
四、另一颗树的子树
题目描述：
给你两棵二叉树
root和subRoot。检验root中是否包含和subRoot具有相同结构和节点值的子树。如果存在，返回true；否则，返回false。二叉树
tree的一棵子树包括tree的某个节点和这个节点的所有后代节点。tree也可以看做它自身的一棵子树。
思路分析：
本题一看没啥思路，这咋搞，很难办对吧。这时，突然想到，能不能放到数组里，然后看小数组是不是大数组的子集。但是，画图分析一下又好像不行。 
唯一的思路断了，这该怎么办？在思索之时，你突然想到：专业的事交给专业的人去干。这道题可不可以分解为这两步：第一步：先找到所有父节点。第二步：在经行判断两棵树是否相同。对于第二步和上题有异曲同工之妙，简单优化即可。
第一步应该怎么办？很简单，直接把节点扔进去就行了，交给第二步去判断就行了，直到找到符合的节点。
所以，这道题看起来很复杂，其实也不简单，对吧。
代码实现：
1. bool istree(struct TreeNode* root, struct TreeNode* subRoot)//判断操作 2. { 3. if(root == NULL && subRoot == NULL) 4. { 5. return true; 6. } 7. if(root == NULL || subRoot == NULL) 8. { 9. return false; 10. } 11. if(root->val != subRoot->val) 12. { 13. return false; 14. } 15. return istree(root->left,subRoot->left) && istree(root->right , subRoot->right); 16. } 17. 18. bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){ 19. if(root == NULL) 20. { 21. return false; 22. } 23. if(root->val == subRoot->val && istree(root,subRoot)) 24. { 25. return true; 26. } 27. return isSubtree(root->left,subRoot) || isSubtree(root->right , subRoot);//找父节点 28. }
题目链接：. - 力扣（LeetCode）
五、二叉树的前序遍历
题目描述：
给你二叉树的根节点
root，返回它节点值的 前序 遍历。
思路分析：
二叉树的前序遍历，这不是说过吗？那好，给大家这个接口，看一看能否在leetcode官方上能不能运行通过。
1. int* preorderTraversal(struct TreeNode* root, int* returnSize) { 2. 3. }
对于以上接口这里解释一下返回值这个问题。一个函数不是只有一个，那咱们应该返回啥，对于该问题，我们要先明白传过来的都代表什么意思。
咱们首先明白，只要实现接口里的大逻辑即可，输入和打印咱们是不必实现的。打印是有leetcode官方写的代码实现的，你要实现打印肯定要知道这个树的的大小对吧。所以，那个returnsize是用来记录大小的。那为什么不用常量呢？因为：形参是实参的一份临时拷贝。要改变形参要传地址，地址需要用指针来接收。
说了这么多，如果读者能够实现，就不用看博主的讲解，如果不行，就一件三连跟着博主继续走即可。
对于我们现在来说，求一个树的节点个数是很简单的一件事，就不在赘述。知道了节点数，便可动态开辟一个数组用来存放数据。那么，我们接下来的难点为：如何把二叉树中的元素放到数组中。
这件事也很简单，就是用前序遍历，把打印换成放元素仅此而已。
代码实现：
1. int preTraversal(struct TreeNode* root) { 2. if (root == NULL) { 3. return 0; 4. } 5. return preTraversal(root->left) + preTraversal(root->right) + 1; 6. } 7. void preorder(struct TreeNode* root, int* a, int* pi) { 8. if (root == NULL) { 9. return; 10. } 11. a[(*pi)++] = root->val; 12. preorder(root->left, a, pi); 13. preorder(root->right, a, pi); 14. } 15. int* preorderTraversal(struct TreeNode* root, int* returnSize) { 16. *returnSize = preTraversal(root); 17. int* a = (int*)malloc(sizeof(int) * (*returnSize)); 18. int i = 0; 19. preorder(root, a, &i); 20. return a; 21. }
题目链接：. - 力扣（LeetCode）
六、二叉树的构建及遍历
题目描述：
描述
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入描述：
输入包括1行字符串，长度不超过100。
输出描述：
可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。
思路分析：
本题要求我们实现一个二叉树，并用中序遍历的方式将其打印出来。这道题很有难度，但有了前面的代码，在此时难度也不是很大了。本题的数据从外部输入，我们还要将其打印。所以，我们要自己实现接受外部的输入和用中序的方式对外打印，这部分代码难度不大，中序打印的类似实现已经讲过，不在赘述。
本题讲解的难点为：构建二叉树。从以上的输入示例中，我们看到有‘#’这样的符号，但打印没它，那，我们可不可以写出以下代码：
1. if(a[(*pi)++] == '#') 2. { 3. return NULL; 4. }
乍一看没啥问题。但仔细想想问题就来了：这个的意思是我每次判断pi都加一，你觉得可行还是不可行。很显然，这不可行。所以，我们要把pi的++放入到{}内才能更好的符合我们的意图。我们放入字符采用的是先序遍历，这部分大家都能掌握，只不过，我们不清楚整颗二叉树的大小，所以，我们每次构建前都要用malloc开辟一下。
代码实现：
1. #include <stdio.h> 2. #include<stdlib.h> 3. typedef char BTDataType; 4. 5. typedef struct BinaryTreeNode { 6. BTDataType data; 7. struct BinaryTreeNode* left; 8. struct BinaryTreeNode* right; 9. } BTNode; 10. BTNode* BTCreatTree(char* a,int* pi) 11. { 12. if(a[*pi] == '#') 13. { 14. (*pi)++; 15. return NULL; 16. } 17. BTNode* root = (BTNode*)malloc(sizeof(BTNode)); 18. root->data = a[(*pi)++]; 19. root->left = BTCreatTree(a,pi); 20. root->right = BTCreatTree(a,pi); 21. return root; 22. } 23. void BTNodePrint(BTNode* root) 24. { 25. if(root == NULL) 26. { 27. return; 28. } 29. BTNodePrint(root->left); 30. printf("%c ",root->data); 31. BTNodePrint(root->right); 32. } 33. int main() { 34. char a[101]; 35. scanf("%s",a); 36. int i = 0; 37. BTNode* ret = BTCreatTree(a,&i); 38. BTNodePrint(ret); 39. return 0; 40. }
题目链接：二叉树遍历_牛客题霸_牛客网
最后：
二叉树的学习，我们目前就告一段落了，后续的进阶内容会在c++部分讲解。今天讲解的题目中最后三道难度较大，还望各位读者在学习完后能够多多练习，这样才能够掌握。如在学习中，有啥问题可在评论区交流，也可私信。期待与读者再会。
完！
