1832-二叉树遍历2

中序遍历否则划分左右子树，层次遍历可以确定根节点，根据层次遍历特点，每个节点可以从左往右按$1$到$n$编号。
可以发现根节点必然是这课树中，编号最小的节点，对子树规律同样适用。
给定序列字母都是唯一的，所以可以先记录每一个字母的位置，在遍历的时候寻找编号最小的字母。
记录每个字母的位置

cin>>s1>>s2; //s1中序遍历  s2层次遍历
for(int i = 0; i < s2.size(); i++){
	v[s2[i]-'A'] = i;
}

子树序列有中序遍历来确定，一开始整个中序序列。

dfs(0,s1.size()-1);

当前中序序列中找出根节点字母（编号最小的节点），然后划分成左右子树继续递归遍历。

void dfs(int l, int r) 
{
	int lz = 2e9,root;
	for(int i = l; i <= r; i++){
		if(v[s1[i] - 'A'] < lz){  //查找对应字母的编号
			lz = v[s1[i] - 'A'];
			root = i;
		}
	}
	cout<<s1[root]; //先序遍历先输出当前子树根节点字母
	if(l<root) dfs(l , root - 1); //遍历左子树
	if(root<r) dfs(root + 1, r);  //遍历右子树
}