共计 2067 个字符，预计需要花费 6 分钟才能阅读完成。
7-3 Left-View of Binary Tree (25 分)
The left-view of a binary tree is a list of nodes obtained by looking at the tree from left hand side and from top down. For example, given a tree shown by the figure, its left-view is {1, 2, 3, 4, 5}
Given the inorder and preorder traversal sequences of a binary tree, you are supposed to output its left-view.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤20), which is the total number of nodes in the tree. Then given in the following 2 lines are the inorder and preorder traversal sequences of the tree, respectively. All the keys in the tree are distinct positive integers in the range of int.
Output Specification:
For each case, print in a line the left-view of the tree. All the numbers in a line are separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.
Sample Input:
2 3 1 5 4 7 8 6
1 2 3 6 7 4 5 8Sample Output:
1 2 3 4 5题目限度：
题目粗心：
给定一颗二叉树的先序和中序序列，须要输入该二叉树的左视图，也就是每一层最右边的结点。
算法思路：
先依据先序和中序进行建树，而后应用档次遍历获取每一个结点的根节点，并应用 currentLevel 记录以后结点所处档次，在结点的档次第一次发生变化的时候就是每一层的最左结点，而后应用 result 数组进行保留，并更新以后节点所处档次，最初输入即可
提交后果：
AC 代码：
#include<cstdio>
#include<queue>
#include<unordered_map>
using namespace std;
struct Node{
int data;
Node* left;
Node* right;
int level;
};
int N;// 节点个数
int pre[30],in[30];
unordered_map<int,int> pos;// 每一个节点在中序序列中的个数
Node* createTree(int preL,int preR,int inL,int inR){if(preL>preR) return nullptr;
Node* root = new Node;
root->data = pre[preL];
int k = pos[root->data];// 根节点在中序中的地位
int numOfLeft = k-inL;
root->left = createTree(preL+1,preL+numOfLeft,inL,k-1);
root->right = createTree(preL+numOfLeft+1,preR,k+1,inR);
return root;
}
int currentLevel = 0;
vector<int> result;
void BFS(Node* root){
root->level = 1;
queue<Node*> q;
q.push(root);
while (!q.empty()){Node* t = q.front();
q.pop();
if(currentLevel!=t->level){
// 达到节点档次转折处
result.push_back(t->data);
currentLevel = t->level;
}
if(t->left){
t->left->level = t->level+1;
q.push(t->left);
}
if(t->right){
t->right->level = t->level+1;
q.push(t->right);
}
}
}
int main(){scanf("%d",&N);
for (int i = 0; i < N; ++i) {scanf("%d",&in[i]);
pos[in[i]] = i;
}
for(int i=0;i<N;++i){scanf("%d",&pre[i]);
}
Node* root = createTree(0,N-1,0,N-1);
BFS(root);
for(int i=0;i<result.size();++i){printf("%d",result[i]);
if(i<result.size()-1) printf(" ");
}
return 0;
}