构建完全二叉树

给你一个整数n，使用1，2，3…n这n个数构造完全二叉树，满足所有节点和父节点的乘积是偶数(根节点除外，因为他没有父节点)，输出构造的二叉树层序遍历的结果。答案不唯一。
输入 4 输出 1 2 4 3

首先记起来，对于层序遍历来说，放置在一个数组里面，对于任何一个父节点i其左儿子为2i+1右儿子为2i+2，直接看代码：
思路就是先偶数后奇数，偶数用完了再看奇数填进去。
根为 1 和 根为 2 都试一遍，如果父节点是奇数就要填偶数，是偶数就先填奇数，奇数没了再填偶数

  2. int tree[MAXN];
  4. int n, odd, even;
  6. void solve() {
  7.     for(int i = 2; i <= n; i++) {
  8.         if(tree[i/2] %  2 == 0 && odd <= n) {
  9.             tree[i] = odd;
  10.             odd+=2;
  11.         } else {
  12.             tree[i] = even;
  13.             even+=2;
  14.         }
  15.     }
  16. }
  18. void output() {
  19.     for(int i = 1; i <= n; i++) {
  20.         cout << tree[i] << " ";
  21.     }
  22. }
  24. bool check() {
  25.     for(int i = 1; i <= n; i++) {
  26.         if(tree[i] > n) {
  27.             return false;
  28.         }
  29.     }
  30.     return true;
  31. }
  33. int main() {
  34.     cin >> n;
  36.     tree[1] = 1;
  37.     odd = 3; even = 2;
  38.     solve();
  40.     if(check()) {
  41.         output();
  42.         return 0;
  43.     }
  44.     tree[1] = 2;
  45.     odd = 1; even = 4;
  46.     solve();
  47.     output();
  49.     return 0;
  50. }

注意，有个小技巧，这里是从数组的第1位开始存，而不是第0位
因此对于树[0,1,2,3,4,5,6]中0不是节点，1是root，因此，此时的对于任何一个节点n，有左儿子为2n右儿子为2n+1，父亲为n/2