AcWing 5422. 二叉树的左视图
原题链接
中等
作者:
YAX_AC
,
2024-12-12 14:58:56
,
所有人可见
,
阅读 8
#include<bits/stdc++.h>
using namespace std;
const int N = 30;
int inorder[N],preorder[N];
unordered_map<int,int> pos,l,r;
int n,st[N];
int build(int inl,int inr,int prel,int prer)
{
int root = preorder[prel];
int k = pos[root];
if(inl<k) l[root] = build(inl,k-1,prel+1,prel+1+k-1-inl);//左子树
if(inr>k) r[root] = build(k+1,inr,prel+1+k-1-inl+1,prer);//右子树
return root;
}
void dfs(int root,int depth)
{ //其实就是从上到下找每一层最左边的结点
if(!st[depth]) st[depth] = root;
if (l.count(root)) dfs(l[root], depth + 1);
if (r.count(root)) dfs(r[root], depth + 1);
}
int main()
{
cin>>n;
for(int i = 0; i<n; i++)
{
cin>>inorder[i];
pos[inorder[i]] = i;
}
for(int i = 0; i<n; i++) cin>>preorder[i];
int root = build(0,n-1,0,n-1);
dfs(root,0);
int i = 0;
int flag = 0;
while(st[i])
{
if(flag == 0) flag = 1;
else cout<<' ';
cout<<st[i];
i++;
}
return 0;
}