二叉树刷题（1）

一、构建二叉树并且遍历

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

输出：c b e g d f a

（1）思路

1、首先读完题目我们需要明白题目的意思：
输入一串字符（前序遍历）根据我们的字符串构建我们的二叉树，然后再中序遍历

构建树的过程如图所示，先创建根节点，然后遍历左子树，然后右子树，所以建树的过程是递归的过程。

2、我们该如何实现呢？
（1）首先我们先创建一个字符数组将我们的字符串放入，因为是数组所以我们需要一个下标来访问我们的数组，但由于我们的建树过程是递归的，所以我们的下标需要在main函数里定义。
（2）然后就进入我们的建树函数里，结束条件是什么呢？大家想如果遇到空是不是就要返回到上一级，所以结束条件就是如果遇到‘#’就返回，并且由于这是在数组里，我们需要下标++。
（3）然后我们就可以开始我们的建根，如果当前数组元素不为“#”就创建根节点，
那根节点的左子树怎么办？那我们就递归，根的left就直接递归，右孩子同理。

这里体现了我么的分置的思想。

（2）代码

#include <stdio.h>
#include<string.h>

typedef struct treenode
{
    char val;
    struct treenode*left;
    struct treenode*right;
}TNode;//定义树的节点

TNode*createtree(char*arr,int*i)
{
    if(arr[*i]=='#')//如果当前节点为空就返回上一级
    {
        (*i)++;
        return NULL;
    }
    TNode*root=(TNode*)malloc(sizeof(TNode));//创建根节点
    root->val=arr[(*i)++];
    root->left=createtree(arr,i);//递归根的左子树
    root->right=createtree(arr,i);//递归根的右子树
    return root;//最后返回根节点即可
}
void midtravel(TNode*root)//中序遍历
{
    if(root==NULL)
        return;
    midtravel(root->left);
    printf("%c ",root->val);
    midtravel(root->right);
}
int main() {
    char arr[100];
    gets(arr);//得到我们的字符串
    int i=0;
    TNode*root=createtree(arr,&i);//为什么这里用i的地址
    //这是因为如果值传递在递归里我们加不上去
    midtravel(root);
    return 0;
}

二、对称二叉树

题目： 给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例：

1、思路

这道题我们的思路是什么呢？

（1）首先我们需要明白什么样的树才是我们的对称二叉树，是不是左子树的左子树等于右子树的右子树，右子树的左子树等于左子树的右子树，那这里跟我们的根节点有关系吗？所以如果我们的根为空就返回true，如果不为空就进入判断左子树与右子树是否是镜像的。
（2）在函数里我们怎么实现呢？首先我们需要判断左子树与右子树是否都为空，如果都为空，那我们的树只有一个根节点，那就返回true，然后我们需要判断是否有一个子树为空，如果有的话那我们的树就不是镜像二叉树。
（3）上面完成以后我们的树就一定有两颗子树，但我们还没有比较它们的值是否相等，如果不相等就返回false，然后再比较左子树的左子树与右子树的右子树是否相等，再比较右子树的左子树是否与左子树的右子树相等即可

2、代码

bool _isSymmetric(struct TreeNode*p,struct TreeNode*q)
 {
    if(p==NULL&&q==NULL)//如果左右子树都为空
        return true;
    if(p==NULL||q==NULL)//第一个if排除了两者都为空的情况，这里判断是否有一个不为空
        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)
 {
    if(root==NULL)//如果根节点为空，就是空树
        return true;
    return _isSymmetric(root->left,root->right);
}

三、相同的树

题目描述
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例：

1、思路

在完成了上面的对称二叉树后这道题就简单很多嘛！
首先我们需要判断两棵树是否都为空以及一个不为空一个为空这两种情况，在判断完上面以后我们的两棵树一定都有根节点，然后我们判断根的值是否相等，最后遍历我们的左树的左树与右数的左树，左树的右树与右树的右树即可。

2、代码

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。
示例：

1、思路

这道题我们首先需要判断树是否为空，如果为空则返回true，如果不是空树，我们就比较左子树的值与根节点的值是否相等，再比较右子树的值与根节点是否相等，如果不相等则返回false，最后递归我们的左子树与右子树。
这里也走的我们的分治的思想。

2、代码

bool isUnivalTree(struct TreeNode* root) {
    if(root==NULL)
        return true;
    if(root->left&&root->val!=root->left->val)
        return false;
    if(root->right&&root->val!=root->right->val)
        return false;
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

五、另一棵树的子树

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

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

示例：

1、思路

这道题其实思路非常的简单，我们不是求是否为子树嘛，那我们可以走一个前序遍历，比较每一个节点作为树与右边的所求的子树，再走一个issametree即可。

2、代码

bool issametrue(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 issametrue(p->left,q->left)&&issametrue(p->right,q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root==NULL&&subRoot==NULL)
        return true;
    if(root==NULL||subRoot==NULL)
        return false;
    if(issametrue(root,subRoot))
        return true;
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}