一.二叉树的前序遍历
想要输出所给值，就要先用数组将数据存储起来，所以这里我们单独创建一个前序遍历函数，将所要数据前序遍历并放入数组，代码如下：
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);
}又因为题目要求返回一个returnSize的指针，所以这里我们再单独创建一个计算树的大小的函数:
int TreeSize(struct TreeNode* root)
{
return root == NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}此题所给函数形参中没有数组，所以我们要单独开辟一段空间来放数组，用malloc函数，最后直接返回数组即可.
代码如下：
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize = TreeSize(root);
int* a = (int*)malloc(sizeof(int) * (*returnSize));
int i = 0;
preOrder(root, a, &i);
return a;
}综上，代码如下：
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));
int i = 0;
preOrder(root, a, &i);
return a;
}二.相同的树
此题判断相同的树，题中函数给的形参给了两个结构体指针，我们可以从指针是否为空处下手来判断是否相等：即两树都为空则相等，若有一个为空则不相等，最后两数的节点值相等，再进行递归即可，代码如下：
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);//其左右子树必须都满足才能返回true
//且最后一直读取读到空都没有返回false,则进入第一个条件判断返回空.
}三.对称二叉树
对称二叉树的判断与上题类似，需要两个结构体指针形参，所以我们再创建一个函数，题目所给函数则用于返回值,代码如下:
bool _isSymmetric(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 _isSymmetric(p->left, q->right)
&& _isSymmetric(p->right, q->left);
}
bool isSymmetric(struct TreeNode* root) {
return _isSymmetric(root->left, root->right);
}四.另一颗树的子树
该题要判断另一棵树是否为本树的子树，需要用到判断树相等的函数：
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)));
}首先，我们要明白：什么情况下我们才会对此树进行判断,那就是只有根节点值相同且通过树相等函数判断返回true的树.代码如下：
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
if(root == NULL)
return false;
if((root->val == subRoot->val)
&& isSameTree(root, subRoot))
{
return true;
}
return isSubtree(root->left, subRoot)//可能为左右子树中任意一个子树，所以用'||'运算符
|| isSubtree(root->right, subRoot);
}五.二叉树遍历
该题要求通过前序遍历创建二叉树，代码如下：
BTNode* CreateTree(char* a, char* pi)
{
if(a[*pi] == '#')
{
(*pi)++;
return NULL;
}
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
root->val = a[(*pi)++];
root->left = CreateTree(a, pi);
root->right = CreateTree(a, pi);
return root;
}本题需要中序遍历打印出二叉树，所以我们写一个中序遍历函数：
void InOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
InOrder(root->left);
printf("%c ", root->val);
InOrder(root->right);
}最后通过主函数将两个函数调用即可，总代码为：
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode
{
char val;
struct TreeNode *left;
struct TreeNode *right;
}BTNode;
BTNode* CreateTree(char* a, char* pi)
{
if(a[*pi] == '#')//当读取到'#'时返回空然后pi++接着读取下一个元素
{
(*pi)++;
return NULL;
}
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
root->val = a[(*pi)++];//将数组里的值放入根节点
root->left = CreateTree(a, pi);//此处为前序遍历
root->right = CreateTree(a, pi);
return root;
}
void InOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
InOrder(root->left);//此处为中序遍历
printf("%c ", root->val);
InOrder(root->right);
}
int main()
{
char a[100];//本题说不超过100字符的空间
scanf("%s", a);
int i = 0;
BTNode* root = CreateTree(a, &i);
InOrder(root);
return 0;
}
