牛客.KY11二叉树遍历、 LeetCode104.二叉树的最大深度 ，110平衡二叉树

二叉树实操小练习~这里对二叉树的遍历要有一定的理解，如果还不熟悉的小伙伴可以看看我的这篇博客：数据结构——二叉树（先序、中序、后序及层次四种遍历（C语言版））超详细~ (???) Q_Q-CSDN博客

?

牛客.KY11二叉树遍历

题目描述：这里要求写出全过程

?思路：这里我们用到两个函数：CreateTree和InOrder，CreateTree将输入的字符串转化为二叉树的前序遍历，InOrder用于对已经创建好的二叉树进行后续遍历并输出。具体实现看如下代码：

#include<stdio.h>
 //二叉树的声明与定义
typedef struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    char val;
}TNode;
 //用于将输入的字符进行前序遍历
TNode* CreateTree(char* a,int* pi)
{
    if(a[*pi]=='#')//这里通过传进来的i来实现对数组a的元素挪动
    {
        ++(*pi);
        return NULL;
    }
 //为开辟一个二叉树而创建的指针变量
    TNode* root=(TNode*)malloc(sizeof(TNode));
    if(root==NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
//将不是'#'的字符赋予此时所对应的二叉树的val,进行前序遍历
    root->val=a[*pi];
    ++(*pi);
    root->left = CreateTree(a,pi);
    root->right = CreateTree(a,pi);
    return root;//返回开辟好的根节点
}
 //对二叉树进行中序遍历并输出，完成题目的任务
void InOrder(TNode* root)
{
    if(root==NULL)
    return;
    InOrder(root->left);
    printf("%c ",root->val);
    InOrder(root->right);
}
 //上述函数都在主函数中实现
int main()
{
    char str[100];
    scanf("%s",str);
    int i=0;
    TNode* root=CreateTree(str,&i);
    InOrder(root);
    return 0;
}

?LeetCode104.二叉树的最大深度

题目描述：

题目所给的二叉树的定义：

?

?基本思路：如果树为空，则深度为0；如果树不为空，则树的深度等于左子树，右子树中的最大深度+1.主要难点在于函数的递归，代码解释：

int maxDepth(struct TreeNode* root) 
{
    if(root==NULL)
      return 0;
//遍历左右子树，直到为空，返回左子树，右子树中较大的后+1（算上自身）
    int leftmaxDepth=maxDepth(root->left);
    int rightmaxDepth=maxDepth(root->right);
    return leftmaxDepth>rightmaxDepth?leftmaxDepth+1:rightmaxDepth+1;
}

?函数递归展开图：（如图中的数为例，红色为递推部分，蓝色为回溯部分）

LeetCode110.平衡二叉树?

题目描述：

?

?题目所定义的二叉树：

思路：整体的左右子树的深度小于等于1，部分的左子树的左右子树的深度小于等于1，部分的右子树的左右子树的深度小于等于1 ，代码解释：

int maxDepth(struct TreeNode* root){
     if(root==NULL)
     return 0;
     int leftmaxDepth=maxDepth(root->left);
     int rightmaxDepth=maxDepth(root->right);
     return leftmaxDepth>rightmaxDepth?leftmaxDepth+1:rightmaxDepth+1;
 }
bool isBalanced(struct TreeNode* root)
{
    if(root==NULL)
    return true;//记录左右子树的最大深度
    int leftmaxDepth=maxDepth(root->left);
    int rightmaxDepth=maxDepth(root->right);
    return abs(leftmaxDepth-rightmaxDepth)<2//分别满足这三个条件，才能满足平衡二叉树
    &&isBalanced(root->left)
    &&isBalanced(root->right);
}

博客到这里也是结束了，喜欢的小伙伴可以点赞加关注支持下博主，这对我真的很重要~~

?

?