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

class Solution:
    def solve(self , xianxu: List[int], zhongxu: List[int]) -> List[int]:
        # write code here
        def reBuildTree(preleft, preright, inleft, inright):
            if preleft > preright: return None
            preroot = preleft
            inroot = index[xianxu[preroot]]
            left_res = inroot - inleft
            
            root = TreeNode(xianxu[preroot])
            
            root.left = reBuildTree(preleft+1, preleft+left_res, inleft, inroot-1)
            root.right = reBuildTree(preleft+left_res+1, preright, inroot+1, inright)
            return root
        
        n = len(xianxu)
        index = {element: i for i, element in enumerate(zhongxu)}
        root = reBuildTree(0, n-1, 0, n-1)#重建二叉树
        
        #层序遍历, 打印每层最右
        queue = [root]
        res = []
        while queue:
            res.append(queue[-1].val)
            tmp = []
            for node in queue:
                if node.left: tmp.append(node.left)
                if node.right: tmp.append(node.right)
            queue = tmp
        return res