class Solution:
    def build(self, l1, r1, l2, r2, pre, med):
        if l1 > r1 or l2 > r2:
            return None
        
        inRoot = med.index(pre[l1])
        root = TreeNode(pre[l1])
        left = inRoot - l2

        root.left = self.build(l1+1, l1+left, l2, inRoot - 1, pre, med)
        root.right = self.build(l1+left+1, r1, inRoot+1, r2, pre, med)

        return root

    def traverse(self, root):
        res = []
        tree = []
        tree.append(root)

        while tree:        
            l = len(tree)
            while l:
                l -= 1
                tmp = tree.pop(0)
                if tmp.left:
                    tree.append(tmp.left)
                if tmp.right:
                    tree.append(tmp.right)
                if l == 0:
                    res.append(tmp.val)

        return res         

    def solve(self , preOrder: List[int], inOrder: List[int]) -> List[int]:
        if not preOrder:
            return None

        root = self.build(0, len(preOrder) - 1, 0, len(inOrder), preOrder, inOrder)

        return self.traverse(root)

解题思路

• 先根据先序遍历和中序遍历结果构建一个树；
• 然后对树进行层次遍历，并找到最右边的节点，得到树的右视图。

复杂度

时间复杂度和空间复杂度都为O（N）。