目录
前言
本章只是二叉树的部分简单练习，对于这部分题目大多比较简单，但重要的不是能过OJ，而是深入理解每一道题的解题原理。
多思考，勤动手，才是正解。对于编程，我们要做到画图半小时，写代码五分钟；而不是写代码五分钟，调试三十分钟。
理解递归思想，分治思想，温故而知新~
1.单值二叉树
根据题目描述，判断二叉树的每个节点的值是否相同。
方法：
- 先判断根节点与左右子节点的值是否相等。
- 进而递归判断左右子树的根节点与左右子节点的值是否相等。
代码如下：?
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.对称二叉树
这道题相当于是上一题的变形版，对称即头节点的左右子树完全相同。
方法：
- 将头节点左右子树看成两颗独立的树
- 然后将左树的左节点与右树的右节点比较，将左树的右节点与右树的左节点比较。
?代码如下：
//子函数，比较两树是否相同
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.二叉树的前序遍历
这里二叉树的前中后序遍历类似，所以只做前序遍历。
与二叉树链式结构中实现的前序遍历不同的是，这里需要将每个节点的值存入数组中。
方法：
- 先找到需要创建数组的大小。
- 根据前序遍历将每个节点的数据存入数组。?
代码如下：
//因为不知道需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.另一棵树的子树
这道题也相当于是判断两颗树是否相同的变形题。
方法：
- 先判断两颗树是否相同。
- 然后判断左右子树是否是与另一颗树相同。
代码如下：
//子函数：判断两棵树是否相同
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函数，需自己调用函数实现。
方法：
- 创建函数创建二叉树节点。
- 创建函数前序遍历二叉树。
代码如下：
#include<stdio.h>
#include<stdlib.h>
//二叉树节点结构体
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;
}