网易笔试_相邻节点乘积为偶数的二叉树

输入整数n；
给出n个节点的完全二叉树的层次遍历，满足：
1.相邻两个父子节点乘积不为奇数

思路：要么第一层放奇数，要么放偶数，之后每两层奇偶间隔。
将完全二叉树中的节点分为两部分，奇数层和偶数层的节点个数分别为m，n；假设这m个节点都为奇数，n都为偶数，即满足所给条件，反之亦然；

那么问题转化为m个节点中放置 偶数还是奇数：

考虑到偶数和偶数相乘不影响结果，因此 m>n 时应该在m节点上放置1~n间的奇数，多余的位置用偶数填充即可，（因为奇数和偶数个数相差不超过1个）

给定n后，需要考虑先放奇数还是偶数，因此先求奇数层和偶数层的节点数，

找到位置多的用来放奇数，空余部分用偶数填充，这样就能够满足题目条件；

  1 //#include 
  2 #include 
  3 #include <string>
  4 #include 
  5 using namespace std;
  6 
  7 int main()
  8 {
  9     int n, x = 0, y = 0;
 10     cin >> n;
 11     int fst=0, sec = 0, last = n;//统计位置
 12     for (int i = 0; last > 0; i++)
 13     {
 14         int tmp;
 15         if (last > (1 << i))
 16         {
 17             tmp = 1 << i;
 18         }else
 19         {
 20             tmp = last;
 21         }
 22         if (i % 2==0)
 23         { // fst+
 24             fst += tmp;
 25         }else
 26         {
 27             sec += tmp;
 28         }
 29         last -= tmp;
 30         cout << fst << "fst   sec" << sec << endl;
 31     }
 32     cout << fst << "fst   sec" << sec << endl;
 33     vector<int> ji, ou;
 34     for (int i = 1; i <= n; i++)
 35     {
 36         if (i % 2)
 37         {
 38             ji.push_back(i);
 39         }
 40         else
 41         {
 42             ou.push_back(i);
 43         }
 44     }
 45     if (fst <= sec)
 46     {
 47         for (int tmp = 0, level = 0; x < ji.size() && y < ou.size(); level++)
 48         { //先打印偶数 ，适用于先打印的位置少
 49             if (level % 2)
 50             { //输出奇数
 51                 for (int i = 0; i < (1 << level) && x < ji.size(); i++)
 52                 {
 53                     cout << ji[x] << " ";
 54                     x++;
 55                 }
 56             }
 57             else
 58             { //偶数
 59                 for (int i = 0; i < (1 << level) && y < ou.size(); i++)
 60                 {
 61                     cout << ou[y] << " ";
 62                     y++;
 63                 }
 64             }
 65         }
 66     }
 67     else//先打印的位置多，因此先打印奇数
 68     {
 69         for (int tmp = 0, level = 0; x < ji.size() && y < ou.size(); level++)
 70         { //先打印奇数 ，适用于先打印的位置多
 71             if (level % 2 == 0)
 72             { //输出奇数
 73                 for (int i = 0; i < (1 << level) && x < ji.size(); i++)
 74                 {
 75                     cout << ji[x] << " ";
 76                     x++;
 77                 }
 78             }
 79             else
 80             { //偶数
 81                 for (int i = 0; i < (1 << level) && y < ou.size(); i++)
 82                 {
 83                     cout << ou[y] << " ";
 84                     y++;
 85                 }
 86             }
 87         }
 88     }
 89 
 90     if (x == ji.size())
 91     {
 92         for (; y < ou.size(); y++)
 93         {
 94             cout << ou[y] << " ";
 95         }
 96     }
 97     else
 98     {
 99         for (; x < ji.size(); x++)
100         {
101             cout << ji[x] << " ";
102         }
103     }
104 
105     return 0;
106 }
107 
108 // cout <

运行结果：

解释：输入n=11，奇数层位置为5个=1+4，偶数层位置6个=2+4，因此在偶数层放奇数

树结构为：

2　　　　　　　　　   L1
1 3　　　　　　　　　L2
4 6 8 10　　　　　　   L3
5 7 9 11　　　　　　　L4