小红的完全二叉树构造【牛客tracker 每日一题】

小红的完全二叉树构造

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

小红想构造一个总共n nn个节点完全二叉树，该二叉树满足以下两个性质：

1. 所有节点的权值值为1 ˜ n 1 \~\ n1˜n的一个排列。
2. 除了根节点以外，每个节点的权值和它父亲的权值的乘积为偶数。

请你帮小红构造出这个二叉树，并按层序遍历的方式打印所有节点。

输入描述：

一个正整数n nn，代表二叉树的节点数量。
2 ≤ n ≤ 10 5 2≤n≤10^52≤n≤105

输出描述：

输出一行n nn个正整数，代表小红构造的二叉树的层序遍历的序列。

示例1

输入：

4

输出：

2 4 3 1

说明：

这棵树的结构如下：

显然，任意节点和它父亲权值的乘积都是偶数

解题思路

本题核心是奇偶性质构造，满足完全二叉树的权值约束条件。根据数学性质：两个数乘积为偶数，当且仅当不同时为奇数。因此构造规则为：除根节点外，所有奇数节点的父亲必须是偶数。完全二叉树采用层序填充，最优方案是将所有偶数优先放在二叉树上层，所有奇数放在下层，彻底避免父子节点同时为奇数。直接按「先输出 1~n 的全部偶数，再输出全部奇数」的顺序排列，即可满足权值排列、完全二叉树结构、乘积约束三大要求，算法时间复杂度O ( n ) O(n)O(n)，高效适配n ≤ 10 5 n \le 10^5n≤105的数据规模。

总结

核心逻辑：利用偶数与任意数相乘为偶数的性质，让所有奇数的父节点都是偶数，满足题目约束。
关键操作：先输出所有偶数，再输出所有奇数，层序填充完全二叉树。
效率保障：线性遍历输出，无冗余计算，轻松处理题目最大数据限制。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll p=1e9+7;constll INF=1e18;constll M=1e6+10;intmain(){ll n;cin>>n;for(ll i=1;i<=n;i++){if(i%2==0)cout<<i<<' ';}for(ll i=n;i>=1;i--){if(i%2!=0)cout<<i<<' ';}return0;}