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

# 前序中序重建树，层次遍历保存每层数组，返回每层数组最后一个元素组成的数组
from queue import Queue
class Solution:
    def reConstructTree(self, preOrder: List[int], inOrder: List[int]) -> TreeNode:
        prelength = len(preOrder)
        inlength = len(inOrder)
        if prelength==0 or inlength==0:
            return None
        root = TreeNode(preOrder[0])
        for i in range(len(inOrder)):
            if preOrder[0] == inOrder[i]:
                leftpre = preOrder[1:i+1]
                leftin = inOrder[:i]
                root.left = self.reConstructTree(leftpre, leftin)
                rightpre = preOrder[i+1:]
                rightin = inOrder[i+1:]
                root.right = self.reConstructTree(rightpre, rightin)
                break
        return root
    def solve(self , preOrder: List[int], inOrder: List[int]) -> List[int]:
        root = self.reConstructTree(preOrder, inOrder)
        q = Queue()
        q.put(root)
        cur = None
        res = []
        while not q.empty():
            row = []
            n = q.qsize()
            for i in range(n):
                cur = q.get()
                row.append(cur.val)
                if cur.left:
                    q.put(cur.left)
                if cur.right:
                    q.put(cur.right)
            res.append(row)
        result = []
        for i in range(len(res)):
            result.append(res[i][-1])
        return result