1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <vector> 5 #include <algorithm> 6  7 using namespace std; 8  9 class Node {10 public:11     int val;12     Node* left;13     Node* right;14 public:15     Node(): val(0), left(NULL), right(NULL) {}16     Node(int _val, Node* _left = NULL, Node* _right = NULL): val(_val), left(_left), right(_right) {}17 };18 19 vector<Node*> build_next_level(vector<Node*> last_level, int &num) {20     vector<Node*> res;21     if (num < 1) return res;22     23     for (auto iter = last_level.begin(); iter != last_level.end(); iter++) {24         Node* parent = *iter;25         26         Node* lchild = new Node();27         res.push_back(lchild);28         parent->left = lchild;29         if (--num < 1) break;30         31         Node* rchild = new Node();32         res.push_back(rchild);33         parent->right= rchild;34         if (--num < 1) break;35     }36     37     return res;38 }39 40 void inorder_traverse(Node* root, int& order) {41     if (root == NULL) return;42     inorder_traverse(root->left, order);43     root->val = order++;44     inorder_traverse(root->right, order);45 }46 47 int main() {48     int cnt;49 50     scanf("%d", &cnt);51     52     vector<int> nums(cnt, 0);53     54     if (cnt < 1) return 0;55     56     for (int i = 0; i<cnt; i++) {57         int num = 0;58         scanf("%d", &num);59         nums[i] = num;60     }61     sort(nums.begin(), nums.end());62     63     vector<vector<Node*> > levels;64 65     vector<Node*> last_level;66     last_level.push_back(new Node());67 68     levels.push_back(last_level);69     70     int node_cnt = cnt - 1; // we already pushed the root node71     while (node_cnt > 0) {72         vector<Node*> cur_level = build_next_level(last_level, node_cnt);73         levels.push_back(cur_level);74         swap(last_level, cur_level);75     }76 77     int order = 0;78     inorder_traverse(levels[0][0], order);79     80     node_cnt = cnt;81     82     for (auto iter_levels = levels.begin(); iter_levels != levels.end(); iter_levels++) {83         vector<Node*>& cur_level = *iter_levels;84         for (auto iter = cur_level.begin(); iter != cur_level.end(); iter++) {85             Node* node = *iter;86             int val = nums[node->val];87             if (--node_cnt > 0) {88                 printf("%d ", val);89             } else {90                 printf("%d\n", val); // last element91             }92         }93     }94     return 0;95 }