我要评论如有不懂的地方，可查阅往期相关文章！
个人主页：小八哥向前冲~
所属专栏：
目录
单值二叉树
题目：
思路：
运用递归，每次递归将根，左孩子，右孩子进行比较！
而最后一次就是左子树，右子树和根的比较！
代码：
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);
}对称二叉树
题目：
思路：
运用递归，将左子树和右子树进行比较！
所以需要分装一个函数比较左子树和右子树。
这个函数里面的左子树的左孩子要和右子树的右孩子比较，左子树的右孩子要和右子树的左孩子比较！
图：
代码：
bool _checksymmetrictree(struct treenode*q,struct treenode*p)
{
//递归
//最后一次递归是q的左子树和p的右子树判断，q的右子树和p的左子树判断
//每次递归看作q的根和p的根判断，q的孩子和p的孩子判断是否相等
if(q==null&&p==null)
return true;
//如果俩根只有一个为空就是假
if(q==null||p==null)
return false;
if(q->val!=p->val)
return false;
return _checksymmetrictree(q->left,p->right)&&
_checksymmetrictree(q->right,p->left);
}
bool checksymmetrictree(struct treenode* root) {
//递归
//最后一次递归是左子树和右子树是否相等
if(root==null)
return true;
return _checksymmetrictree(root->left,root->right);
}计算二叉树的深度
题目：
思路：
我们不难看出：树的高度==高的子树的高度+1。
代码：
int calculatedepth(struct treenode* root) {
//左子树和右子树比较，大的子树加+1就是高度
if(root==null)
return 0;
int leftheight=calculatedepth(root->left);
int rightheight=calculatedepth(root->right);
return leftheight>rightheight?leftheight+1:rightheight+1;
}二叉树的前序遍历
题目：
前序遍历二叉树，将值存到数组中。
思路：
为了开辟的数组不大不小，我们计算树节点总数，然后进行前序遍历一个一个将树节点数值写入数组中。
以此则中序遍历和后序遍历也是如此！
代码：
int treesize(struct treenode*root)
{
//左子树节点+右子树节点+1
return root==null?0:treesize(root->left)+treesize(root->right)+1;
}
void preorder(struct treenode*root,int*a,int*i)
{
if(root==null)
return;
a[(*i)++]=root->val;
preorder(root->left,a,i);
preorder(root->right,a,i);
}
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;
}相同二叉树
题目：
思路：
运用递归，分别将俩棵树的根和根比较，左子树和左子树比较，右子树和右子树比较！
图：
代码：
bool issametree(struct treenode* p, struct treenode* q) {
//p的左子树和q的左子树比较，p的右子树和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 sametree(struct treenode*q,struct treenode*p)
{
if(q==null&&p==null)
return true;
if(q==null||p==null)
return false;
if(q->val!=p->val)
return false;
return sametree(q->left,p->left)&&sametree(q->right,p->right);
}
bool issubtree(struct treenode* root, struct treenode* subroot){
//找出所有子树，再和另一棵子树比较是否相同
if(root==null)
return false;
//值相等时，开始比较树是否相等
if(root->val==subroot->val&&sametree(root,subroot))
return true;
//在左子树和右子树中能找到就行
return issubtree(root->left,subroot)
||issubtree(root->right,subroot);
}二叉树的构建和遍历
题目：
思路：
遍历读取数组的每个值，前序遍历将树建好，最后中序遍历二叉树打印！
代码：
#include <stdio.h>
#include<stdlib.h>
typedef struct treenode {
struct treenode* left;
struct treenode* right;
char val;
} tnode;
void inoder(tnode*root)
{
if(root==null)
return;
inoder(root->left);
printf("%c ",root->val);
inoder(root->right);
}
tnode*createtree(char*a,int*i)
{
if(a[(*i)]=='#')
{
(*i)++;
return null;
}
tnode*node=(tnode*)malloc(sizeof(tnode));
node->val=a[(*i)++];
node->left=createtree(a, i);
node->right=createtree(a, i);
return node;
}
int main() {
char a[100];
scanf("%s",a);
int i=0;
tnode*root=createtree(a,&i);
inoder(root);
return 0;
}翻转二叉树
题目：
思路：
递归，先将左子树交换，再将右子树交换！
代码：
struct treenode* inverttree(struct treenode* root) {
if(root==null)
return null;
struct treenode*tmp;
tmp=root->left;
root->left=root->right;
root->right=tmp;
//交换左子树
if(root->left)
inverttree(root->left);
//交换右子树
if(root->right)
inverttree(root->right);
return root;
}判断平衡二叉树
题目：
代码：
int treeheight(struct treenode* p) {
if (p == null)
return 0;
int leftheight = treeheight(p->left);
int rightheight = treeheight(p->right);
return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
}
bool isbalanced(struct treenode* root) {
if (root == null)
return true;
return isbalanced(root->left) && isbalanced(root->right)&&
abs(treeheight(root->left) - treeheight(root->right)) <= 1;
}今天的题目，你都学会了吗？我们下期见！
发表评论