#先还原二叉链表(其实有不用还原的更厉害的方法,见本人博客)
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
# 求二叉树的右视图
# @param xianxu int整型一维数组 先序遍历
# @param zhongxu int整型一维数组 中序遍历
# @return int整型一维数组
#它娘的终于弄明白它自动给的这行代码是干什么用的了,费老大劲儿
#就是提示你先序和中序的两个遍历列表已经给出,可以直接用,只等你return结果列表了
class Solution:
    def solve(self , xianxu: List[int], zhongxu: List[int]) -> List[int]:
        # write code here
        class binTreeNode: #定义结点
            def __init__(self):
                self.data='#'
                self.left=None
                self.right=None
        def createOrder(xianxu, zhongxu): #先还原二叉链表
            if zhongxu == []: #这两句可以换成if not zhongxu:return
                return None
            else:
                root = binTreeNode()
                root.data = xianxu[0]
                ind = zhongxu.index(root.data)
                root.left = createOrder(xianxu[1:], zhongxu[0:ind])
                root.right = createOrder(xianxu[ind + 1:], zhongxu[ind + 1:])
                return root
        def rightView(root,level): #生成右视图列表,一层一层进,同一层的后面的覆盖前面的
            if root==None:
                return
            elif level>len(res):
                res.append(root.data)
            elif level<=len(res):
                res[level-1]=(root.data) #每一层只能提取保留一个元素,新提取的覆盖旧的,层数是从1开始的,所以元素下标要层数减1
            rightView(root.left,level+1) #分别遍历左右子树
            rightView(root.right, level+1)
        root = createOrder(xianxu, zhongxu) #调用各函数
        level=1;global res;res=[] #列表、字典、集合之类的数据类型可以如此使用global即在外面声明一下即可,字符串、数字、元组等数据类型不可这样用,须在子函数内部用global声明
        rightView(root,level)
        return(res) #若不采用全局变量则res始终为空