目录

前言

1.单值二叉树

2.相同的树

3.对称二叉树

4.二叉树的前序遍历

5.另一棵树的子树

6.平衡二叉树 

7.二叉树遍历

前言

本章只是二叉树的部分简单练习，对于这部分题目大多比较简单，但重要的不是能过OJ，而是深入理解每一道题的解题原理。

多思考，勤动手，才是正解。对于编程，我们要做到画图半小时，写代码五分钟；而不是写代码五分钟，调试三十分钟。

理解递归思想，分治思想，温故而知新~

1.单值二叉树

单值二叉树

根据题目描述，判断二叉树的每个节点的值是否相同。

方法：

1. 先判断根节点与左右子节点的值是否相等。
2. 进而递归判断左右子树的根节点与左右子节点的值是否相等。

代码如下： 

bool isUnivalTree(struct TreeNode* root){    1.空树也是单值，返回真    if(root == NULL)    {        return true;    }    2.判断根节点与左子节点，前提是左子树不为空，为空不需比较    if(root->left&&root->val != root->left->val)    {        return false;    }    3.判断根节点与右子节点    if(root->right&&root->val != root->right->val)    {        return false;    }    //递归继续判断左右子树    return isUnivalTree(root->left)&&isUnivalTree(root->right);}

2.相同的树

相同的树

这道题比较简单，先比较根节点的值，然后递归比较左右子树的节点是否相同即可。

直接上代码吧：

bool isSameTree(struct TreeNode* p, struct TreeNode* q){        //1.两树都为空返回真    if(p == NULL && q == NULL)    {        return true;    }        //2.两树不相同有两种情况    //(1)两树节点的值不相等    //(2)两树一个节点为空，一个不为空    if((p == NULL || q == NULL) || (p->val != q->val ))    {        return false;    }    //若当前节点相等，则递归比较两树左右子树    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);}

3.对称二叉树

对称二叉树

这道题相当于是上一题的变形版，对称即头节点的左右子树完全相同。

方法：

1. 将头节点左右子树看成两颗独立的树
2. 然后将左树的左节点与右树的右节点比较，将左树的右节点与右树的左节点比较。

 代码如下：

//子函数，比较两树是否相同bool _isSymmetric(struct TreeNode*left, struct TreeNode*right){    if(left == NULL && right == NULL)    {        return true;    }    if((left == NULL || right == NULL) || (left->val != right->val))    {        return false;    }    return _isSymmetric(left->left,right->right)&&_isSymmetric(left->right,right->left);}bool isSymmetric(struct TreeNode* root){    //1.空树也是对称二叉树，返回真    if(root == NULL)    {        return 0;    }    //2.因为我们需要比较两树是否相同，需传两个参数，这里需要创建子函数    return _isSymmetric(root->left,root->right);    }

4.二叉树的前序遍历

二叉树的前序遍历

二叉树的中序遍历

二叉树的后序遍历

这里二叉树的前中后序遍历类似，所以只做前序遍历。

与二叉树链式结构中实现的前序遍历不同的是，这里需要将每个节点的值存入数组中。

方法：

1. 先找到需要创建数组的大小。
2. 根据前序遍历将每个节点的数据存入数组。 

代码如下：

//因为不知道需malloc数组的大小，先创建求二叉树节点个数的函数(前面介绍过，这里就不再讲)int TreeSize(struct TreeNode* root){    if(root==NULL)    {        return 0;    }    return TreeSize(root->left)+TreeSize(root->right)+1;}//前序遍历子函数void PrevOrder(struct TreeNode* root,int*arr,int*pi){    if(root==NULL)    {        return;    }    arr[(*pi)++] = root->val;//将节点数据放入数组                             //因为将数据放入数组后，下标位置会向后移动，                             //需改变i的值，所以要传i的地址    PrevOrder(root->left,arr,pi);    PrevOrder(root->right,arr,pi);}//前序遍历int* preorderTraversal(struct TreeNode* root, int* returnSize){    //1.求节点个数    int size = TreeSize(root);    //创建数组    int*arr = (int*)malloc(sizeof(int)*size);    //输出型参数    *returnSize = size;    int i =0;    //同样，因为参数限制，递归时不能使用本函数，所以需要创建子函数实现    PrevOrder(root,arr,&i);    return arr;}

5.另一棵树的子树

另一颗子树

这道题也相当于是判断两颗树是否相同的变形题。

方法：

1. 先判断两颗树是否相同。
2. 然后判断左右子树是否是与另一颗树相同。

代码如下：

//子函数：判断两棵树是否相同bool _isSubtree(struct TreeNode*a, struct TreeNode*b){    if(a==NULL&&b==NULL)    {        return true;    }    if((a==NULL||b==NULL)||a->val!=b->val)    {        return false;    }    return _isSubtree(a->left,b->left)&&_isSubtree(a->right,b->right);}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){        //1.root为空则肯定不是子树，返回false    if(root == NULL)    {        return false;    }    //2.判断两颗树是否相同    if(_isSubtree(root,subRoot))    {        return true;    }    //3.判断左右子树与另一颗是否相同，只需要一颗相同即可    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);    }

6.平衡二叉树 

平衡二叉树

这道题是二叉树链式结构中求二叉树深度的变形。

方法：

利用分治思想：

先求根节点的左右子树的深度之差的绝对值是否大于1。

再求左右子节点的子树深度之差。

//求二叉树深度int TreeDepth(struct TreeNode* root){    if(root == NULL)    {        return 0;    }    int leftdepth = TreeDepth(root->left);    int rightdepth = TreeDepth(root->right);    return leftdepth>rightdepth?leftdepth+1:rightdepth+1;}bool isBalanced(struct TreeNode* root){    if(root==NULL)    {        return true;    }    //左子树深度    int l = TreeDepth(root->left);    //右子树深度    int r = TreeDepth(root->right);    //判断是否是平衡二叉树    int x = l-r;    if(x < 0)    {        x = r-l;    }    if(x>1)    {        return false;    }    //继续判断左右子树的子树    return isBalanced(root->left)&&isBalanced(root->right);}

7.二叉树遍历

二叉树遍历

这道题设计的是IO型，所以需要我们自己写结构体和main函数，需自己调用函数实现。

方法：

1. 创建函数创建二叉树节点。
2. 创建函数前序遍历二叉树。

代码如下：

#include#include//二叉树节点结构体struct BTNode{    char val;    struct BTNode*left;    struct BTNode*right};//创建节点，以及按照数组的每个值创建二叉树struct BTNode* CreatNode(char* str,int*pi){    //当字符为"#"时表示该节点为空    if(str[*pi]=="#")    {        (*pi)++;        return NULL;    }        //创建节点    struct BTNode*root = (struct BTNode*)malloc(sizeof(struct BTNode));    //将字符串字符放入节点    root->val = str[(*pi)++];    //递归创建左右节点    root->left = CreatNode(str,pi);    root->right = CreatNode(str,pi);    return root;}//前序遍历输出节点void Inorder(struct BTNode*root){    if(root==NULL)    {        return;    }        Inorder(root->left);    //输出节点    printf("%c ",root->val);    Inorder(root->right);}int main(){    char str[100] = {0};    int i = 0;    while(scanf("%s",str)!=EOF)    {                struct BTNode*root = CreatNode(str,&i);        Inorder(root);    }    return 0;}