1.二叉树的遍历 

来源：牛客网

解题思路：这里首先第一个遇到的难点就是如何创建一棵树， 我们知道树的创建首先就是找到根结点，然后创建左右子树，所以这里是利用前序创建一棵树。

根据题目，#就是一个叶子结点，所以遍历到'#'就直接返回NULL，反之递归创建树。

当然中序遍历就很简单了，也是使用递归。代码如下：

#include <stdio.h>
#include<stdlib.h>

typedef struct BinaryTree
{
     struct BinaryTree* left;
     struct BinaryTree* right;
     char val;
}BTNode;

//前序找根节点
BTNode* CreateTree(char* a,int* 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);
}

int main() 
{
    char a[100];
    scanf("%s",a);

    int i = 0;
    BTNode* root = CreateTree(a,&i);
    InOrder(root);

    return 0;
}

2. 二叉树的前序遍历

来源：leetcode

解题思路： 首先要动态申请一块空间存储二叉树中的数据，当然要知道申请的空间大小，就要创建一个TreeSize函数计算，然后设计一个前序遍历函数，利用递归实现。中序与后序只是变换了顺序，本质不改变。

代码如下

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;
}

3. 二叉树的中序遍历

来源：leetcode

int TreeSize(struct TreeNode* root)
{
    return root == NULL ? 0 : 
    TreeSize(root->left) + TreeSize(root->right) + 1;
}

void InOrder(struct TreeNode*root,int* a,int* pi)
{
    if(root == NULL)
    {
        return;
    }
    
    InOrder(root->left,a,pi);
    a[(*pi)++] = root->val;
    InOrder(root->right,a,pi);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) 
{    
    *returnSize = TreeSize(root);
    int* a = (int*)malloc(sizeof(int) * (*returnSize));

    int i = 0;
    InOrder(root,a,&i);

    return a;
}

4. 二叉树的后序遍历

来源：leetcode

int TreeSize(struct TreeNode *root)
{
    return root == NULL ? 0 :TreeSize(root->left) + TreeSize(root->right) + 1;
}

void PostOrder(struct TreeNode *root,int* a,int*pi)
{
    if(root == NULL)
    {
        return ;
    }

    PostOrder(root->left,a,pi);
    PostOrder(root->right,a,pi);
    a[(*pi)++] = root->val;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) 
{    
    *returnSize = TreeSize(root);
    int* a = (int*)malloc(sizeof(int) * (*returnSize));

    int i = 0;
    PostOrder(root,a,&i);

    return a;
}

5. 另一棵树的子树

来源：leetcode

思路解析： 判断是否为子树可以从左子树到右子树，只要有一个个符合就 停止判断，所以首先实现一个判等函数isSameTree函数，然后判断原树是否为空，为空则直接返回NULL，反之判断是否满足根节点的值与整棵子树是否同时相同，最后递归调用原函数即可。

代码如下：

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 NULL;
    }

    if(root->val == subRoot->val 
    && isSameTree(root,subRoot))
    {
        return true;
    }
    return isSubtree(root->left,subRoot)
    || isSubtree(root->right,subRoot);
}