1099 build a binary search tree (30 points)

The main idea of the topic ： Each node of the tree is determined by children , Insert the given value so that it is a binary search tree .

Flattening the binary search tree is orderly , That is, the middle order traversal is ordered . According to this nature , Go through it in middle order , Save node number and depth , After sorting, the hierarchy traversal ( Sort by depth and number )

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node
{
	int l,r,h,idx,val;
}e[200];
vector<node>ans;
vector<int>v(200);
int n,cnt;
void dfs(int u,int h,int idx)
{   
	if(e[u].l != -1) dfs(e[u].l,h + 1,idx << 1);
	ans.push_back({0,0,h,idx,v[cnt ++]});// Traverse in middle order 
	if(e[u].r != -1) dfs(e[u].r,h + 1,idx << 1 | 1);
}
int main()
{
    cin >> n;
	for(int i = 0; i < n; i ++) cin >> e[i].l >> e[i].r;
	for(int i = 0; i < n; i ++) cin >> v[i];
	sort(v.begin(),v.begin() + n);
	dfs(0,0,1);
	sort(ans.begin(),ans.end(),[](node a,node b)
	{
		if(a.h != b.h) return a.h < b.h;return a.idx < b.idx;
	});
	for(int i = 0; i < ans.size(); i ++)
	{
		if(i != 0) cout << ' ';
		cout << ans[i].val;
	}
	return 0;

}