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

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

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