👩💻博客主页：风起 风落的博客主页
✨欢迎关注🖱点赞🎀收藏⭐留言✒
👕参考网站：牛客网
💻首发时间：🎞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; }
在这里插入图片描述主要是分治思想，大事化小，把其化成带有根节点的AA的左子树，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###
在这里插入图片描述
递归展开图
在这里插入图片描述
