PAT 1064 Complete Binary Search Tree

 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 node

71     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
", val); // last element

91             }

92         }

93     }

94     return 0;

95 }