1174 Left-View of Binary Tree – PAT甲级真题-CSDN博客

文章讲述了如何根据给定的二叉树的中序遍历和前序遍历序列，通过递归算法计算并输出其左视图。作者给出了C++代码实现，利用pre和in数组存储遍历结果，t数组存储每一层最左边的节点值。

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:

8
2 3 1 5 4 7 8 6
1 2 3 6 7 4 5 8

Sample Output:

1 2 3 4 5

题目大意：二叉树的左视图是通过从左侧向右上方查看树而获得的结点列表。例如，给定如图所示的树，其左视图为{1,2,3,4,5}。给定二叉树的中序遍历和前序遍历序列，输出其左视图。

分析：pre与in数组分别存储前序和中序遍历的结果，t存储某一层最左边的结点值，ins、ine分别表示当前操作在中序遍历数组中的起始位置与终止位置，prerootindex表示当前的子树根结点在前缀序列中的位置，level表示现在处于第几层，pos表示当前子树根结点在中序遍历数组中的位置。用前序和中序遍历的序列可以唯一确定一棵树。由于是从左到右的顺序遍历树的，所以每次判断当前层的t数组中没有元素（值为0）的时候，就表示这一层最左边的结点是现在这一个。

#include <iostream>
using namespace std;
int N, pre[30], in[30], t[30];
void deal(int ins, int ine, int prerootindex, int level) {
    if (ins > ine) return;
    if (t[level] == 0) {
        t[level] = pre[prerootindex];
    }
    int pos = ins;
    while(in[pos] != pre[prerootindex]) ++pos;
    deal(ins, pos - 1, prerootindex + 1, level + 1);
    deal(pos + 1, ine, prerootindex + 1 + pos - ins, level + 1);
}
int main(){
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> in[i];
    for (int i = 1; i <= N; i++) cin >> pre[i];
    deal(1, N, 1, 1);
    for (int i = 1; t[i]; i++) {
        if (i != 1) cout << ' ';
        cout << t[i];
    }
    return 0;
}