【每日刷题】Day73
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 2583. 二叉树中的第 K 大层和 - 力扣（LeetCode）
2. 1325. 删除给定值的叶子节点 - 力扣（LeetCode）
3. 1161. 最大层内元素和 - 力扣（LeetCode）
1. 2583. 二叉树中的第 K 大层和 - 力扣（LeetCode）
//思路：深度优先遍历求层和+排序。深度优先遍历二叉树，以当前层为下标将当前层当前节点的值累加到数组对应下标位置。将所有层和求出后对数组排序，返回第K大层和。
typedef struct TreeNode TN;
//层和
void _kthLargestLevelSum(TN* root,long long* arr,int high)
{
if(!root)
return;
arr[high]+=root->val;
_kthLargestLevelSum(root->left,arr,high+1);
_kthLargestLevelSum(root->right,arr,high+1);
}
//二叉树最大深度
int BinaryTreeHigh(TN* root)
{
if(!root)
return 0;
int left = BinaryTreeHigh(root->left);
int right = BinaryTreeHigh(root->right);
return 1+(left>right?left:right);
}
void Swap(long long* x, long long* y)
{
long long tmp = *x;
*x = *y;
*y = tmp;
}
//向下调整
void AdjustDown(long long* arr, int parents,int size)
{
int child = parents * 2 + 1;
while (child < size)
{
if (child + 1 < size && arr[child + 1] > arr[child])
{
child++;
}
if (arr[child] > arr[parents])
{
Swap(&arr[child], &arr[parents]);
}
else
{
break;
}
parents = child;
child = parents * 2 + 1;
}
}
//堆排序
void HeapSort(long long* arr, int size)
{
//向下调整建堆
for (int i = (size - 2) / 2; i >= 0; i--)
{
AdjustDown(arr, i, size);
}
while (size)
{
Swap(&arr[0], &arr[size - 1]);
size--;
AdjustDown(arr, 0, size);
}
}
long long kthLargestLevelSum(struct TreeNode* root, int k)
{
if(BinaryTreeHigh(root)<k)//如果不足K层，直接返回-1
return -1;
long long* arr = (long long*)calloc(100000,sizeof(long long));
_kthLargestLevelSum(root,arr,0);//求出所有层和
HeapSort(arr,100000);
return arr[100000-k];
}
2. 1325. 删除给定值的叶子节点 - 力扣（LeetCode）
//思路：深度优先遍历。遍历二叉树，根据题目要求更改每个节点的left、right指针的指向。
//① 如果遍历到的节点为NULL，直接返回NULL，让其上一个节点的left或right指向NULL
//② 如果遍历到的节点为叶子节点且其值＝ target，也返回NULL，让其上一个节点的left或right指向NULL
//③ 如果遍历到的节点不是上述两个情况，则直接返回当前节点
typedef struct TreeNode TN;
//判断是否为叶子节点bool IsLeafNode(TN* root)
{
return !root->left&&!root->right;
}
//修改每个节点的left和right
TN* _removeLeafNodes(TN* root,int target)
{
if(!root)
return NULL;//情况①
root->left = _removeLeafNodes(root->left,target);
root->right = _removeLeafNodes(root->right,target);
if(root->val==target&&IsLeafNode(root))//情况②
return NULL;
return root;//情况③
}
struct TreeNode* removeLeafNodes(struct TreeNode* root, int target)
{
_removeLeafNodes(root,target);
if(root->val==target&&IsLeafNode(root))
return NULL;
return root;
}
3. 1161. 最大层内元素和 - 力扣（LeetCode）
//思路：深度优先遍历+哈希。遍历二叉树，将每层的和以层数为下标存入数组中。随后遍历数组，找到下标最小(层数最小)且和最大的下标。
//注意：哈希数组中的所有初值必须为绝对最小(也就是任何层和都不能比它小)，这样才能正确找到最小层数且最大层和的下标。
typedef struct TreeNode TN;
void _maxLevelSum(TN* root,int* hash,int k)
{
if(!root)
return;
if(hash[k]<=-10000000)//由于需要求层和，因此需要将随机值初始化。
hash[k]=0;
hash[k]+=root->val;
_maxLevelSum(root->left,hash,k+1);
_maxLevelSum(root->right,hash,k+1);
}
int maxLevelSum(struct TreeNode* root)
{
int* hash = (int*)malloc(sizeof(int)*1000);//开辟好后，数组中为随机值，其为一非常小的数字，满足我们上面的注意事项
_maxLevelSum(root,hash,0);
int max = -1000000000;
for(int i = 0;i<1000;i++)
{
if(hash[i]>max)//找到最大层和的值
max = hash[i];
}
int* ans = (int*)malloc(sizeof(int)*1);
for(int i = 0;i<1000;i++)
{
if(hash[i]==max)//找到第一个＝最大层和的下标，即为最小下标(最小层数)
{
ans[0] = i+1;//因为树根节点在第一层，而数组下标从0开始，因此结果需要+1
break;
}
}
return ans[0];
}
