👩‍💻博客主页：风起 风落的博客主页

✨欢迎关注🖱点赞🎀收藏⭐留言✒

👕参考网站：牛客网

💻首发时间：🎞2022年8月18日🎠

🎨你的收入跟你的不可替代成正比

🀄如果觉得博主的文章还不错的话，请三连支持一下博主哦
💬给大家介绍一个求职刷题收割offer的地方👉点击网站

@TOC

一、104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


int maxDepth(struct TreeNode* root){
    if(root==NULL)
    {
        return 0;
    }
   int left=maxDepth(root->left);
   int right=maxDepth(root->right);
   return left>right?left+1:right+1;
}

主要是分治思想，大事化小，把其化成带有根节点的A
A的左子树，A的右子树 ,再分别判断左子树与右子树的最大深度，
取两者最大值+1即二叉树的最大深度

递归展开图

二、110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int maxDepth(struct TreeNode* root){
    if(root==NULL)
    {
        return 0;
    }
   int left=maxDepth(root->left);
   int right=maxDepth(root->right);
   return left>right?left+1:right+1;
}
bool isBalanced(struct TreeNode* root){
   if(root==NULL)
   {
       return true;
   }
   int leftdepth=maxDepth(root->left);
   int rightdepth=maxDepth(root->right);
   return abs(leftdepth-rightdepth)<2
   &&isBalanced(root->left)
   &&isBalanced(root->right);
}

本题也是使用了二叉树的最大深度，我本来的想法是跟上题差不多
求根节点的左子树 和根节点的右子树，但是后来我发现忽略了每个节点都要差一这个条件。
这道题也是使用了c语言求绝对值所使用的 abs
只有满足该点的左子树和左子树相差小于2并且左子树与右子树本身递归也相差小于2才成立

递归展开图

三、二叉树遍历

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述:
输入包括1行字符串，长度不超过100。
输出描述:
可能有多组测试数据，对于每组数据，
输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。
每个输出结果占一行。

示例1
输入
abc##de#g##f###
输出
c b e g d f a

#include<stdio.h>
#include<stdlib.h>
typedef struct treenode
{
    char val;
    struct treenode*left;
    struct treenode*right;
}BTnode;
BTnode*tree(char *a,int*i)//创建二叉树
{
    if(a[*i]=='#')
    {
        (*i)++;//为#看作一个空格 ，跳过
        return NULL;
    }
    BTnode*root=(BTnode*)malloc(sizeof(BTnode));//在函数内创建二叉树结构体类型，最大程度上知道了二叉树的节点个数
        root->val=a[*i];
        (*i)++;//这里不要忘记将i+1 ，将a的值指向下一个
        root->left=tree(a,i);//两次循环调用
        root->right=tree(a,i);
    return root;//返回结构体指针，可以找到二叉树
}
void inorder(BTnode*root)//二叉树的中序遍历 递归
{
    if(root==NULL)
    {
        return ;
    }
    inorder(root->left);//左子树
    printf("%c ",root->val);//根
    inorder(root->right);//右子树
}
int main()
{
    char arr[40]={0};
    scanf("%s",arr);
    int i=0;//这里我们想要通过函数得到i的值 ，需要传址调用
    BTnode*root=tree(arr,&i);
    inorder(root);
    return 0;
}

首先就以本题的例子来说明，’#'代表空格
abc##de#g##f###

递归展开图