作者:小卢
专栏:《Leetcode》
喜欢的话:世间因为少年的挺身而出,而更加瑰丽。 ——《人民日报》
1609. 奇偶树
1609. 奇偶树
题目描述:
如果一棵二叉树满足下述几个条件,则可以称为 奇偶树 :
二叉树根节点所在层下标为 0 ,根的子节点所在层下标为 1 ,根的孙节点所在层下标为 2 ,依此类推。
偶数下标 层上的所有节点的值都是 奇 整数,从左到右按顺序 严格递增
奇数下标 层上的所有节点的值都是 偶 整数,从左到右按顺序 严格递减
给你二叉树的根节点,如果二叉树为 奇偶树 ,则返回 true ,否则返回 false 。
示例:
思路:
奇偶树:就当层数level为奇数,节点递减,当层数level为偶数,节点递增
很明显本题需要用到层序遍历。
判断一棵二叉树是否为奇偶树,需要考虑两个条件,一是节点值的奇偶性,二是节点值的单调性,这两个条件都由层下标的奇偶性决定。因此,需要维护搜索到的层下标,以及对于每一层搜索都需要维护上一个节点值。
如果当前层下标是偶数,则要求当前层的所有节点的值都是奇数,且节点值从左到右严格递增。如果遇到节点值是偶数,或者当前节点值小于等于上一个节点值,则二叉树一定不是奇偶树。
如果当前层下标是奇数,则要求当前层的所有节点的值都是偶数,且节点值从左到右严格递减。如果遇到节点值是奇数,或者当前节点值大于等于上一个节点值,则二叉树一定不是奇偶树。
如果二叉树的所有节点都满足奇偶树的条件,则二叉树是奇偶树。
更详细的可以看看注释,我写很详细!!!
代码:
bool isEvenOddTree(struct TreeNode* root) {
//Queue为队列
//level为层数
//head为二叉树的遍历位置
//tail为队列的遍历位置
struct TreeNode* Queue[100010];
int level = 0;
int head = 0;
int tail = 0;
Queue[head++] = root;
while (tail < head)//当队列的位置tail大于二叉树的位置head遍历完成
{
//front为每次出队列的元素
//size为队列的有效长度
int size = head - tail;
//prev为上一个节点的val
//INT_MAX为int类型的最大值,INT_MIN为int类型的最小值
//奇偶树:当level为奇数,节点是递减的,所以第一个节点要大于第二个节点
//而在层序遍历中,最左边的节点一定是小于INT_MAX
//同理可得,当leve为偶数,最左边的节点大于INT_MIN
int prev = level % 2 == 0 ? INT_MIN : INT_MAX;
for (int i = 0; i < size; i++)
{
struct TreeNode* front = Queue[tail++];
if (level % 2 == (front->val) % 2)//level为奇数,节点为偶数,level为偶数,节点为奇数
return false;
if ((level % 2 == 0 && prev >= front->val) || (level % 2 == 1 && prev <= front->val))
return false;//当level为奇数,节点是递减的,当level为偶数,节点是递增的
prev = front->val;
if (front->left)
Queue[head++] = front->left;
if (front->right)
Queue[head++] = front->right;
}
level++;
}
return true;
}//LeetCode1609
1122. 数组的相对排序
1122. 数组的相对排序
题目描述:
给你两个数组,arr1 和 arr2,arr2 中的元素各不相同,arr2 中的每个元素都出现在 arr1 中。
对 arr1 中的元素进行排序,使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
示例:
文章来源:https://www.toymoban.com/news/detail-408551.html
代码:文章来源地址https://www.toymoban.com/news/detail-408551.html
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* relativeSortArray(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize) {
int upper = 0;
for (int i = 0; i < arr1Size; i++) {
upper = fmax(upper, arr1[i]);
}
int frequency[upper + 1];
memset(frequency, 0, sizeof(frequency));
for (int i = 0; i < arr1Size; i++) {
frequency[arr1[i]]++;
}
int* ans = malloc(sizeof(int) * arr1Size);
*returnSize = 0;
for (int i = 0; i < arr2Size; i++) {
int x = arr2[i];
for (int j = 0; j < frequency[x]; j++) {
ans[(*returnSize)++] = x;
}
frequency[x] = 0;
}
for (int x = 0; x <= upper; x++) {
for (int i = 0; i < frequency[x]; i++) {
ans[(*returnSize)++] = x;
}
}
return ans;
}
到了这里,关于【LeetCode】1609. 奇偶树、1122. 数组的相对排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!