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

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;
}

#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;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版