小红的完全二叉树构造【牛客tracker 每日一题】
小红的完全二叉树构造
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
小红想构造一个总共n nn个节点完全二叉树，该二叉树满足以下两个性质：
- 所有节点的权值值为1 ˜ n 1 \~\ n1˜n的一个排列。
- 除了根节点以外，每个节点的权值和它父亲的权值的乘积为偶数。
请你帮小红构造出这个二叉树，并按层序遍历的方式打印所有节点。
输入描述：
一个正整数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;}