1099 Build A Binary Search Tree 30分
题目描述:告诉了BST的结点下标关系、结点值,求BST的层次遍历序列。
vector<int> in; // 保存中序序列 int Tree[105][2]; // 保存结点与左右孩子结点之间的下标 map<int,vector<int>> mp; // 保存每一层的结点信息 int cnt = 0; void deal(int idx,int level){ if(Tree[idx][0] != -1){ deal(Tree[idx][0],level+1); } int inRoot_val = in[cnt ++]; mp[level].push_back(inRoot_val); if(Tree[idx][1] != -1){ deal(Tree[idx][1],level+1); } } void ex(){ int n; cin >> n; in.resize(n); int root = 0; for(int i=0;i<n;i++){ cin >> Tree[i][0] >> Tree[i][1]; } for(int i=0;i<n;i++){ cin >> in[i]; } sort(in.begin(),in.end()); deal(root,1); for(auto it= mp.begin();it!=mp.end();it++){ if(it != mp.begin()){ cout << " "; } if(it->second.size() != 0){ for(int i=0;i<it->second.size();i++){ cout << it->second[i]; if(i+1 != it->second.size()){ cout << " "; } } } } }