#先还原二叉链表(其实有不用还原的更厉害的方法,见本人博客)
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
# 求二叉树的右视图
# @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始终为空