PTA 浪漫侧影 Python

前置知识：

对于不一定是完全二叉树，根据已知的中序+后序（前序）遍历顺序来建树（ps：中序一定是需要的）

参考大佬博客：已知中序和前序（或后序）遍历结果生成树_勿忘初心丶的博客-CSDN博客_已知中序序列和后序序列

解题思路：

对于树的每一层，最左端的对应着左侧影，最右端对应着右侧影。

因此也不需要建树，只需要把每一层的元素存在一个数组 arr 中，左侧影为arr[0],右侧影为 arr[-1]。

例如题目中的arr存放的数据为:[[1],[6,2],[7,3],[8,4],[5]]

那么我们就可以自行理解一下，左侧影1,6,7,8,5,右侧影1,2,3,4,5了......

题目：

我们将二叉树的“侧影”定义为从一侧能看到的所有结点从上到下形成的序列。例如下图这棵二叉树，其右视图就是 { 1, 2, 3, 4, 5 }，左视图就是 { 1, 6, 7, 8, 5 }。

于是让我们首先通过一棵二叉树的中序遍历序列和后序遍历序列构建出一棵树，然后你要输出这棵树的左视图和右视图。

输入格式：

输入第一行给出一个正整数 N (≤20)，为树中的结点个数。随后在两行中先后给出树的中序遍历和后序遍历序列。树中所有键值都不相同，其数值大小无关紧要，都不超过 int 的范围。

输出格式：

第一行输出右视图，第二行输出左视图，格式如样例所示。

输入样例：

8 6 8 7 4 5 1 3 2

8 5 4 7 6 3 2 1

输出样例：

R: 1 2 3 4 5

L: 1 6 7 8 5

AC代码：

def build(mid,behind,line,len_mid):
    global arr
    element = behind.pop()
    arr[line].append(element)
    index = mid.index(element)
    if index<=1:
        for i in range(index):arr[line+1].append(mid[i])
    else:build(mid[:index],behind[:index],line+1,index)
    if len_mid - index -1 <=1:
        for i in range(len_mid-index-1):arr[line+1].append(mid[index+1+i])
    else:build(mid[index+1:],behind[index:],line+1,len_mid-index-1)


n = int(input())
arr = [[] for i in range(n)]
mid = list(map(int,input().split()))
behind = list(map(int,input().split()))
build(mid,behind,0,n)
beh = 'R: '
pre = 'L: '
for i in range(n):
    if arr[i]:
        beh += str(arr[i][-1])+' '
        pre += str(arr[i][0])+' '
    else:break
print(beh[:-1])
print(pre[:-1])