前言：本章将通过六道来自LeetCode/牛客网中的二叉树相关算法题来介绍数据结构中二叉树在算法题中的应用。

1.单值二叉树

OJ链接
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

思路分析：

我们知道“”具有传递性，如果ab&&bc，可以推出ac，一个父亲跟左右孩子的值相等

题解：

bool isUnivalTree(struct TreeNode* root){
    if(root==NULL)
    {
        return true;
    }
    if(root->left&&root->left->val!=root->val)  //如果左不为空，且左值等于根节点的值
    {
        return false;
    }
    if(root->right&&root->right->val!=root->val)
    {
        return false;
    }
    return isUnivalTree(root->left)&&isUnivalTree(root->right);  //“==”具有传递性，神奇的递归
}

2.二叉树的前序遍历

OJ链接
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

思路分析：

首先需要malloc一块内存给数组arr，数组arr用于保存二叉树前序遍历结果，这时候写个TreeSize求下二叉树节点个数。

然后写一个子函数，递归调用进行遍历（记住i需要传指针）。

题解：

/** * Note: The returned array must be malloced, assume caller calls free(). */
  //输出型参数，不需要再手动进行打印
int  TreeSize(struct TreeNode*root)  //求出二叉树中节点个数
{
    if(root==NULL)
    {
        return 0;
    }
    return TreeSize(root->left)+TreeSize(root->right)+1;
}

void _preorderTraversal(struct TreeNode* root, int *arr,int* i)
{
    if(root==NULL)
    {
        return;
    }
    arr[(*i)++]=root->val;

    _preorderTraversal(root->left,arr,i);
    _preorderTraversal(root->right,arr,i);

}

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize=TreeSize(root);
   int* arr=malloc(sizeof(int)* *returnSize);
   int i=0;
   _preorderTraversal(root,arr,&i);//这边i务必传指针，每个递归调用栈帧中都有一个i，传值的话下一层++i不会对上一层造成影响

   return arr;
}

3.相同的树

OJ链接
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

思路分析：

分治：大问题分解成小问题，小问题再继续分解，直到分割成不可再分割的子问题。

考虑：如果都为空，结果为真；若一个为空，结果为假；若均不为空，但是节点数值不一样，结果为假。

最后递归调用（分治思想）。

题解：

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

判断下上述算法的时间/空间复杂度？

4.对称二叉树

OJ链接
给定一个二叉树，检查它是否是镜像对称的。

思路分析：

先判断根节点是否为空，是就返回true，不是就对左右子树进行递归判断，而对左右子树进行递归就类似上一题了。

题解：

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){
    if(root==NULL)
    {
        return true;
    }
    return _isSymmetric(root->left,root->right);
}

5.另一棵子树

OJ链接
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

思路分析：

先判断根节点是否为空，是则返回false；遍历root，拿到每个子树的跟，跟subRoot比较

以如下两颗数为例：

递归过程如下：

题解：

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){
    //遍历root，拿到每个子树的跟，跟subRoot比较
    if(root==NULL)
    {
        return false;
    }
    if(isSameTree(root,subRoot))
    {
        return true;
    }
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

6.二叉树遍历

OJ链接
描述

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC/#/#DE/#G/#/#F/#/#/# 其中“/#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述：

输入包括1行字符串，长度不超过100。

输出描述：

可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。

思路分析：

题干啥也没给，所以首先根据输入的字符串str[]，“逆前序遍历”复原出原本二叉树结构，然后中序遍历打印该二叉树。

题解：

#include<stdio.h>

struct TreeNode
{
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* CreatTree(char* str,int* pi)
{
    if(str[*pi]=='#')
    {
        (*pi)++;
        return NULL;
    }
    struct TreeNode*root=(struct TreeNode*)
        malloc(sizeof(struct TreeNode));
    root->val=str[(*pi)++];
    root->left=CreatTree(str, pi);
    root->right=CreatTree(str, pi);
    
    return root;
}

void InOrder(struct TreeNode* root)
{
    if(root==NULL)
    {
        return;
    }
    InOrder(root->left);
    printf("%c ",root->val);
    InOrder(root->right);
}
    
    
int main()
{
    char str[100];
    scanf("%s",str);
    int i=0;
    struct TreeNode* root=CreatTree(str,&i);
    InOrder(root);
}