Leetcode -1609.奇偶树
题目：如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：
二叉树根节点所在层下标为 0 ，根的子节点所在层下标为 1 ，根的孙节点所在层下标为 2 ，依此类推。
偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增
奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减
给你二叉树的根节点，如果二叉树为 奇偶树 ，则返回 true ，否则返回 false 。
示例 1：
输入：root = [1, 10, 4, 3, null, 7, 9, 12, 8, 6, null, null, 2]
输出：true
解释：每一层的节点值分别是：
0 层：[1]
1 层：[10, 4]
2 层：[3, 7, 9]
3 层：[12, 8, 6, 2]
由于 0 层和 2 层上的节点值都是奇数且严格递增，而 1 层和 3 层上的节点值都是偶数且严格递减，因此这是一棵奇偶树。
示例 2：
输入：root = [5, 4, 2, 3, 3, 7]
输出：false
解释：每一层的节点值分别是：
0 层：[5]
1 层：[4, 2]
2 层：[3, 3, 7]
2 层上的节点值不满足严格递增的条件，所以这不是一棵奇偶树。
示例 3：
输入：root = [5, 9, 1, 3, 5, 7]
输出：false
解释：1 层上的节点值应为偶数。
示例 4：
输入：root = [1]
输出：true
示例 5：
输入：root = [11, 8, 6, 1, 3, 9, 11, 30, 20, 18, 16, 12, 10, 4, 2, 17]
输出：true
提示：
树中节点数在范围[1, 10^5] 内
1 <= Node.val <= 10^6
思路：利用循环队列实现，相当于层序遍历判断，一层一层判断；思路如下：
bool isEvenOddTree(struct TreeNode* root) { // 先开辟足够空间 struct TreeNode* queue[100002]; // front 为队头，出数据从队头出，减减 front 即可 // rear 为队尾，进数据从队尾进，加加 rear 即可 // prev 记录前驱节点 int front = 0, rear = 0, prev; // 记录该层是奇还是偶；奇为1 ，偶为0 int EvenOdd = 0; // 开始先进 root 节点 queue[rear++] = root; // front 不等于 rear，说明队列不为空，继续进入循环 while (front != rear) { // cnt 为当前队列的有效节点个数 int cnt = rear - front; // 如果是奇树，定义 prev 为整型的最大值，方便判断每一层上的节点严格递增 if (EvenOdd) prev = INT_MAX; // 偶数则定义 prev 为整型的最小值，方便判断每一层上的节点严格递减 else prev = INT_MIN; // 在有效节点个数的范围内循环 for (int i = 0; i < cnt; i++) { // 出队头的节点 root = queue[front++]; // 判断是奇树还是偶树，按照对应的树做对应的判断，不满足则返回 false if ((EvenOdd == 0) && (root->val % 2 == 0 || prev >= root->val)) return false; if ((EvenOdd == 1) && (root->val % 2 != 0 || prev <= root->val)) return false; prev = root->val; // 每出一个数据，判断如果 root 的左子树或右子树不为空，那就进队列 if (root->left) queue[rear++] = root->left; if (root->right) queue[rear++] = root->right; } // 控制奇树层和偶树层 EvenOdd = (EvenOdd + 1) % 2; } return true; }
Leetcode -1122.数组的相对排序
题目：给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
示例 1：
输入：arr1 = [2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19], arr2 = [2, 1, 4, 3, 9, 6]
输出：[2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19]
示例 2:
输入：arr1 = [28, 6, 22, 8, 44, 17], arr2 = [22, 28, 8, 6]
输出：[22, 28, 8, 6, 17, 44]
提示：
1 <= arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
arr2 中的元素 arr2[i] 各不相同
arr2 中的每个元素 arr2[i] 都出现在 arr1 中
思路：用hash数组记录arr1中出现元素出现的次数，通过arr2中出现的元素，判断其在arr1中出现的次数，覆盖掉原来arr1中的元素，直到其出现的次数减到0；最后再判断arr1中没有在arr2中出现的元素，直接补在后面即可；代码如下：
int* relativeSortArray(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize) { // hash数组记录 arr1 数组中出现的元素的次数 // pos 记录覆盖当前 arr1 数组的长度 int hash[1001] = { 0 }; int pos = 0; // 记录 arr1 数组中出现的元素的次数 for (int i = 0; i < arr1Size; i++) { hash[arr1[i]]++; } // 遍历 arr2 数组，arr2 中的元素如果在 arr1 中出现，就将 arr2 的元素覆盖在 arr1 中 // 然后出现的次数减减，一直覆盖直到在 hash 数组中出现的次数为0 for (int i = 0; i < arr2Size; i++) { while (hash[arr2[i]] != 0) { arr1[pos++] = arr2[i]; hash[arr2[i]]--; } } // 判断 arr1 中没在 arr2 中出现的元素 // 直接在 arr1 后面补上 for (int i = 0; i < 1001; i++) { while (hash[i] != 0) { arr1[pos++] = i; hash[i]--; } } // 最后返回 arr1 *returnSize = arr1Size; return arr1; }
