【每日刷题】Day49
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 110. 平衡二叉树 - 力扣（LeetCode）
2. 501. 二叉搜索树中的众数 - 力扣（LeetCode）
3. 637. 二叉树的层平均值 - 力扣（LeetCode）
1. 110. 平衡二叉树 - 力扣（LeetCode）
//思路：平衡二叉树：对于树中每个结点都满足 左、右子树深度差值不超过1。因此我们递归遍历树的每一个结点，判断每一个结点处是否满足平衡二叉树，只要有一个不满足直接return false。
int TreeHigh(struct TreeNode* root)
{
if(root==NULL)
return 0;
int HighLeft = TreeHigh(root->left);
int HighRight = TreeHigh(root->right);
return 1+(HighLeft>HighRight?HighLeft:HighRight);
}
bool isBalanced(struct TreeNode* root)
{
if(root==NULL)
return true;
int HighLeft = TreeHigh(root->left);
int HighRight = TreeHigh(root->right);
int tmp = abs(HighLeft-HighRight);
if(tmp>1)
return false;
return isBalanced(root->left)&&isBalanced(root->right);
}
2. 501. 二叉搜索树中的众数 - 力扣（LeetCode）
//思路：哈希表。本题很容易想到使用哈希表存储每个数出现的次数，找出出现次数最多的数。但因为数中的值可能为负数，因此我们需要对哈希表的键进行调整。
void FindMode(struct TreeNode* root,int* arr)
{
if(root==NULL)
return;
arr[root->val+100000]+=1;//将所有负数转变为正数
FindMode(root->left,arr);
FindMode(root->right,arr);
}
int* findMode(struct TreeNode* root, int* returnSize)
{
int hash[200001] = {0};
FindMode(root,hash);
int max = 0;
int* ans = (int*)malloc(sizeof(int)*10000);
int size = 0;
for(int i = 0;i<200001;i++)
{
max = max>hash[i]?max:hash[i];
}
for(int i = 0;i<200001;i++)
{
if(hash[i]==max)
{
ans[size++] = i-100000;//将原为负数的值更改回去
}
}
*returnSize = size;
return ans;
}
3. 637. 二叉树的层平均值 - 力扣（LeetCode）
//思路：使用一个数组存储二叉树每一层结点个数，随后对二叉树进行层序遍历，每次根据每层结点个数将结点的值进行累加，然后除去当前层的结点个数，从而算出每层的平均值，存储进答案数组中返回。注：本题思路需要先明白二叉树层序遍历的实现。
typedef struct TreeNode BT;
typedef struct TreeNode* QDataType;
//队列节点
typedef struct listnode
{
QDataType val;
struct listnode* next;
}LN;
//队列头尾指针
typedef struct Queque
{
LN* phead;
LN* ptail;
int size;
}QE;
//队列初始化
void QueInit(QE* qe)
{
assert(qe);
qe->phead = NULL;
qe->ptail = NULL;
qe->size = 0;
}
//入列
void QuePush(QE* qe, QDataType x)
{
assert(qe);
LN* newnode = (LN*)malloc(sizeof(LN));
if (newnode == NULL)
{
perror("malloc:");
exit(-1);
}
newnode->next = NULL;
newnode->val = x;
if (qe->phead == NULL)
{
qe->phead = qe->ptail = newnode;
}
else
{
qe->ptail->next = newnode;
qe->ptail = qe->ptail->next;
}
qe->size++;
}
//出列
void QuePop(QE* qe)
{
assert(qe);
assert(qe->phead != NULL);
assert(qe->size > 0);
LN* tmp = qe->phead->next;
free(qe->phead);
qe->phead = tmp;
qe->size--;
}
//获取列头元素
QDataType QueGetHead(QE* qe)
{
assert(qe);
assert(qe->phead != NULL);
return qe->phead->val;
}
//判断队列是否为空
bool QueEmpty(QE* qe)
{
assert(qe);
return qe->size == 0;
}
//层序遍历二叉树计算平均值(队列实现层序遍历)
void SequenceTraverse(BT* root,int* arr,int size,double* ans,int* count)
{
QE q;
QueInit(&q);
if (root)
QuePush(&q, root);
int i = 0;
while (i<size)
{
double tmp = 0;
int n = arr[i];//记录当前层的节点数
while(n)
{
QDataType front = QueGetHead(&q);//获取队头元素
QuePop(&q);//将队头元素出列
if(front)
tmp+=front->val;//累加
if(front)
{
QuePush(&q, front->left);//继续将当前结点的left和right结点入队列
QuePush(&q, front->right);
n--;
}
}
tmp/=arr[i];//计算平均值
ans[(*count)++] = tmp;
i++;
}
}
//求二叉树第K层结点个数
int BinaryTreeKSize(BT* root,int k)
{
if (root == NULL)
return 0;
if (k == 0)
return 1;
return BinaryTreeKSize(root->left, k - 1) + BinaryTreeKSize(root->right, k - 1);
}
double* averageOfLevels(struct TreeNode* root, int* returnSize)
{
int ksize[10000] = {0};
int size = 0;
do
{
int ret = BinaryTreeKSize(root,size);
ksize[size++] = ret;
}while(ksize[size-1]);//将二叉树每层节点数存储起来
double* ans = (double*)malloc(sizeof(double)*10000);
int count = 0;
SequenceTraverse(root,ksize,size,ans,&count);
*returnSize = count-1;
return ans;
}
