大家好，这里是小编的博客频道
小编的博客：就爱学编程
很高兴在
CSDN这个大家庭与大家相识，希望能在这里与大家共同进步，共同收获更好的自己！！！
目录
废话不多说，我们直接看题。
1.
（1）题目描述
（2）解题思路
首先我们需要了解什么是二叉树的前序遍历：按照访问根节点——左子树——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。
定义 preorder(root) 表示当前遍历到 root 节点的答案。按照定义，我们只要首先将 root 节点的值加入答案，然后递归调用 preorder(root.left) 来遍历 root 节点的左子树，最后递归调用 preorder(root.right) 来遍历 root 节点的右子树即可，递归终止的条件为碰到空节点。
代码实现：
int TreeSize(struct TreeNode* root){
return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
void preorder(struct TreeNode* root, int* a, int* pi){
if(root == NULL) return;
a[(*pi)++] = root->val;
preorder(root->left, a, pi);
preorder(root->right, a, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize = TreeSize(root);
int* a = (int*)malloc(sizeof(int) * (*returnSize));
assert(a);
int i = 0;
preorder(root, a, &i);
return a;
}
2.对称二叉树
（1）题目描述
（2）解题思路
如果一个树的左子树与右子树镜像对称，那么这个树是对称的。因此，该问题可以转化为：两个树在什么情况下互为镜像？
如果同时满足下面的条件，两个树互为镜像：
- 它们的两个根结点具有相同的值
- 每个树的右子树都与另一个树的左子树镜像对称
代码实现：
bool check(struct TreeNode*p, struct TreeNode*q) {
if (!p && !q) return true;
if (!p || !q) return false;
return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
}
bool isSymmetric(struct TreeNode* root) {
return check(root->left, root->right);
}
3.另一棵树的子树
（1）题目描述
（2）解题思路
深度优先搜索枚举 s 中的每一个节点，判断这个点的子树是否和 t 相等。如何判断一个节点的子树是否和 t 相等呢，我们又需要做一次深度优先搜索来检查，即让两个指针一开始先指向该节点和 t 的根，然后「同步移动」两根指针来「同步遍历」这两棵树，判断对应位置是否相等。
代买实现：
//判断两棵树是否相同
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
if(p == NULL && q == NULL) return true;
if((p == NULL || q == NULL) || (p->val != q->val)) return false;
else 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));
}
4.二叉树的构建及遍历
（1）题目描述
（2）解题思路
根据题目的要求来即可
代码实现：
#include <stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct TreeNode{
struct TreeNode* left;
struct TreeNode* right;
char val;
}TR;
//建树
TR* CreateTreeNode(char* arr, size_t* pi){
if(arr[*pi] == '#')
{
++(*pi);
return NULL;
}
TR* root = (TR*)malloc(sizeof(TR));
root->val = arr[*pi];
++(*pi);
root->left = CreateTreeNode(arr, pi);
root->right = CreateTreeNode(arr, pi);
return root;
}
//中序遍历
void InOrder(TR* root){
if(root == NULL) return;
InOrder(root->left);
printf("%c ", root->val);
InOrder(root->right);
}
int main() {
char arr[100];
scanf("%s", arr);
//建树
size_t i = 0;
TR* root = CreateTreeNode(arr, &i);
//中序遍历
InOrder(root);
return 0;
}