【LeetCode】1609. 奇偶树、1122. 数组的相对排序

淡淡的烟草味﹌ 2024-03-25 20:53 17阅读 0赞

>  作者：小卢
> 
> 专栏：《Leetcode》
> 
> 喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
> 
> ![7d63d497b5114103b3dd7633a1ba4731.jpeg][]
> 
> --------------------

## 1609. 奇偶树 ##

[1609. 奇偶树][1609.]

题目描述：

如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：

二叉树根节点所在层下标为 0 ，根的子节点所在层下标为 1 ，根的孙节点所在层下标为 2 ，依此类推。  
偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增  
奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减  
给你二叉树的根节点，如果二叉树为 奇偶树 ，则返回 true ，否则返回 false 。

示例：

![030b7149cdbd493d90437e7a5620c021.png][]

思路：

奇偶树：就当层数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. 数组的相对排序][1122.]

题目描述：

给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。

对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

示例：

![ee3a1d0ae3104965a150cafc6d9de2eb.png][]

代码：

/**
     * 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;
    }

[7d63d497b5114103b3dd7633a1ba4731.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/793f299a3ac2496aa3db2b0494190bf5.png
[1609.]: https://leetcode.cn/problems/even-odd-tree/
[030b7149cdbd493d90437e7a5620c021.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/2c384bf1001c48fa9065f9bde15cfa43.png
[1122.]: https://leetcode.cn/problems/relative-sort-array/
[ee3a1d0ae3104965a150cafc6d9de2eb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/e5b4e6f1b7894a41bb413ff3017c18dd.png