【Leetcode -1609.奇偶树 -1122.数组的相对排序】

简介: 【Leetcode -1609.奇偶树 -1122.数组的相对排序】

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;
    }
目录
相关文章
|
3天前
|
C++ Python
二刷力扣--数组
二刷力扣--数组
|
4天前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
4天前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
|
4天前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
4天前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
3天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
3天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
4天前
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
|
4天前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
4天前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词