一、单值二叉树
航班直达！
前序遍历的思想。
思路：先判断左右节点是否存在，再判断根分别和左右节点的值是
否相等。
1.如果左子节点存在，但是值不等于根节点的值，返回false
2.如果右子节点存在，但是值不等于根节点的值，返回false
如果相等，递归其左子节点和右子节点。
不拿如果子节点的值等于根节点的值这个条件来判断的原因是：
就算子节点的值和根节点的相等，也不能代表什么，因为还需要判断下一层子节点的值都与它们的根节点的值相等才行，这样才能达到判断整棵树的值都相等的效果。
即：先判断结构，再判断值
注意：如果根节点为空，返回true，特殊情况特殊处理。
//思路：前序遍历的思想，根先与左右比较，如果不同，直接返回假
//再让左子树与左子树的左右子树比较，这样分治下去
bool isUnivalTree(struct TreeNode* root)
{
//空树返回真，因为最后叶子节点的左右子树都为空
if(root == NULL)
{
return true;
}
//两个不能写反了，先判断是否为空再比较数据
if(root->left!=NULL && root->left->val != root->val)
{
return false;
}
if(root->right!=NULL && root->right->val != root->val)
{
return false;
}
return isUnivalTree(root->left)
&& isUnivalTree(root->right);
}
二、二叉树最大深度
航班直达！
思路：分别递归根节点的左子节点和右子节点，每次递归一层就计算一层深度，然后比较左右子节点的高度，让大的值+1，（+1是加根节点自己的高度）
//思路：前序遍历的思想+分治算法
//把整棵树看作根左子树右子树组成，先计算左子树的高度和右子树的高度，
//比较之后，大的再加上自己的高度
//左子树又让左子树的左右子树比较高度
int maxDepth(struct TreeNode* root)
{
if(root == NULL)
{
return 0;
}
//注意：千万不能写成：
//return maxDepth(root->left)>maxDepth(root->right)?maxDepth(root->left)+1:maxDepth(root->right)+1;
//这样写虽然能通过，但是效率大大降低，因为同样的事情重复了好多次
int lheight = maxDepth(root->left);
int rheight = maxDepth(root->right);
return lheight>rheight?lheight+1:rheight+1;
}
三、翻转二叉树
航班直达！
思路：后序遍历的思想，先从最底层开始交换：
root->left = right,root->right = left
如果递归到叶子节点了，该叶子节点的左右子树都为NULL，交换它们结果是一样的
所以最底层交换完了，回到上一层，左子树交换完了，到右子树，最后返回根节点即可
//思路：后序遍历的思想，先从最底层开始交换：
//root->left = right,root->right = left
//如果递归到叶子节点了，该叶子节点的左右子树都为NULL，交换它们结果是一样的
//所以最底层交换完了，回到上一层，左子树交换完了，到右子树，最后返回根节点即可
struct TreeNode* invertTree(struct TreeNode* root)
{
if(root == NULL)
{
return NULL;
}
struct TreeNode*left = invertTree(root->left);
struct TreeNode*right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
四、检查两棵树是否相同
航班直达！
思路：最好是前序遍历：只要从根节点开始，有一个节点的结构不相同，或者值不相同，都返回假
先判断结构，再判断值
判断值的时候，如果值为真，也没有什么意义，因为还需要不断往下比较
所以应该判断值为假，返回false比较合适
//思路：最好是前序遍历：只要从根节点开始，有一个节点的结构不相同，或者值不相同，都返回假
//先判断结构，再判断值
//判断值的时候，如果值为真，也没有什么意义，因为还需要不断往下比较
//所以应该判断值为假，返回false比较合适
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
//1.先判断结构
//两个都是空树，返回真
if(p == NULL && q == NULL)
{
return true;
}
//来到这里，必有一假，其中一个是空树，返回假
if(p == NULL || q == NULL)
{
return false;
}
//2.结构判断完了，判断值
if(p->val!= q->val )
{
return false;
}
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
五、对称二叉树
航班直达！
思路：根节点无需判断，应该写一个函数单独判断两颗子树是否对称的问题
对称问题其实就是判断两颗子树是否相同问题的变形，判断两颗子树是否相同，就是递归两个子树的左和左，右和右，
判断两颗子树是否对称，是递归两个子树的左和右，右和左
先判断结构对称，再判断数据对称
bool isSymmetricalBinaryTree(struct TreeNode* l,struct TreeNode* r)
{
//两个都为空
if(!l && !r)
{
return true;
}
//其中一个为空
if(l == NULL || r == NULL)
{
return false;
}
//都不为空
if(l->val!=r->val)
{
return false;
}
return isSymmetricalBinaryTree(l->left,r->right) &&isSymmetricalBinaryTree(l->right,r->left);
}
bool isSymmetric(struct TreeNode* root)
{
//题目说了不是空树
// if(root == NULL)
// {
// return true;
// }
return isSymmetricalBinaryTree(root->left,root->right);
}
六、二叉树遍历
航班直达！
文章来源：https://www.toymoban.com/news/detail-416932.html
这道题是IO型，需要完全实现输入输出。
思路：按照题目要求，按前序遍历的思想建立一棵树。
然后以中序遍历打印出来，注意：打印完后需要销毁树。文章来源地址https://www.toymoban.com/news/detail-416932.html
#include <stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef char BTDataType;
struct BTNode
{
struct BTNode*left;
struct BTNode*right;
BTDataType data;
};
struct BTNode* CreatTree(BTDataType*a,int *pi)
{
//（*pi)++不能放在判断这里++，要放在里面,因为如果a[*pi]不为'#'，也一样++了，到下面pi这里就++两次了。
if(a[(*pi)] =='#')
{
(*pi)++;
return NULL;
}
struct BTNode*root = (struct BTNode*)malloc(sizeof(struct BTNode));
assert(root!=NULL);
root->data = a[(*pi)++];
root->left = CreatTree(a,pi);
root->right = CreatTree(a,pi);
return root;
}
void InOrder(struct BTNode*root)
{
if(root == NULL)
{
return ;
}
InOrder(root->left);
printf("%c ",root->data);
InOrder(root->right);
}
void BTDestroy(struct BTNode*root)
{
if(root == NULL)
{
return ;
}
BTDestroy(root->left);
BTDestroy(root->right);
free(root);
//置空没效果
root = NULL;
}
int main() {
BTDataType a[100];
scanf("%s",a);
int i =0;
struct BTNode*root = CreatTree(a,&i);
InOrder(root);
BTDestroy(root);
root = NULL;
return 0;
}
到了这里，关于【深入理解二叉树OJ题】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
