爱站程序员基地PAT A1099 Build A Binary Search Tree
- 给了树形和节点值确定一棵BST，输出层序。层序如果不想bfs的话，可以用二维数组收集每层的节点值，保证收集的时候都是先访问左边再访问右边
- 所以可以放在一个dfs中解决：节点值排序变成中序序列，使用题目所给结构中序遍历(dfs)，同时传个层数lv下去，则过程中访问到的节点对应中序序列的顺序，把对应的节点值放到level数组相应的层中即可
#include<iostream>#include<vector>#include<algorithm>using namespace std;struct Node{int left,right;};vector<Node> vn;vector<int> in;vector<vector<int> > level;int cnt = 0,max_lv = 0;void dfs(int idx,int lv){if(lv > max_lv) max_lv = lv;if(vn[idx].left != -1) dfs(vn[idx].left,lv + 1);level[lv].push_back(in[cnt ++]);if(vn[idx].right != -1) dfs(vn[idx].right,lv + 1);}int main(){int N;cin >> N;vn.resize(N);in.resize(N);level.resize(N);for(int i = 0;i < N;i ++) cin >> vn[i].left >> vn[i].right;for(int i = 0;i < N;i ++) cin >> in[i];sort(in.begin(),in.end());dfs(0,0);cout << level[0][0];for(int i = 1;i <= max_lv;i ++){for(int j = 0;j < level[i].size();j ++) cout << \' \' << level[i][j];}return 0;}
