题解 | #输出二叉树的右视图#

思路：写树类 根据先序中序构建二叉树 然后使用层次遍历

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 求二叉树的右视图
# @param xianxu int整型一维数组 先序遍历
# @param zhongxu int整型一维数组 中序遍历
# @return int整型一维数组
#
class Solution:
    def solve(self , xianxu: List[int], zhongxu: List[int]) -> List[int]:
        # 先恢复二叉树 然后打印层次遍历的最后一个节点
        if len(xianxu)==1 or  len(zhongxu)==1:return xianxu
        def huifu(xianxu,zhongxu):
            if len(xianxu)==0 or len(xianxu)==0:return None
            root=treeNode(xianxu[0])
            root_idx=zhongxu.index(root.val)
            root.left=huifu(xianxu[1:root_idx+1],zhongxu[:root_idx])
            root.right=huifu(xianxu[root_idx+1:],zhongxu[root_idx+1:])
            return root
        def ceng_order(root):
            if root is None:return None
            stack,res=[root],[]
            while stack:
                ceng_nodes=[]
                for i in range(len(stack)):
                    node=stack.pop(0)
                    ceng_nodes.append(node.val)
                    if node.left:stack.append(node.left)
                    if node.right:stack.append(node.right)
                res.append(ceng_nodes[-1])
            return res
        root= huifu(xianxu,zhongxu)
        res=ceng_order(root)
        return res
class treeNode():
    def __init__(self,val,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right