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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 求二叉树的右视图
# @param preOrder int整型一维数组 先序遍历
# @param inOrder int整型一维数组 中序遍历
# @return int整型一维数组
#
from collections import defaultdict
 
class Solution:
    def buildTree(self, pre_order, l1, r1, mid_order, l2, r2):
        if l1 > r1 or l2 > r2:
            return None
        root =TreeNode(pre_order[l1])
        root_index = 0
        for i in range(l2, r2+1):
            if mid_order[i] == pre_order[l1]:
                root_index = i
                break
        left_size = root_index - l2
        right_size = r2 - root_index
        root.left = self.buildTree(pre_order, l1 + 1, l1 + left_size, mid_order, l2, l2 + left_size - 1)
        root.right = self.buildTree(pre_order, r1 - right_size + 1, r1, mid_order, root_index + 1, r2)
        return root

    def rightSideView(self, root):
        mp = defaultdict(int)
        max_depth = -1
        nodes, depths = list(), list()
        nodes.append(root)
        depths.append(0)

        while nodes:
            node = nodes[-1]
            nodes.pop()
            depth = depths[-1]
            depths.pop()

            if node:
                max_depth = max([max_depth, depth])
                if mp[depth] == 0:
                    mp[depth] = node.val
                nodes.append(node.left)
                nodes.append(node.right)
                depths.append(depth + 1)
                depths.append(depth + 1)

        res = []
        for i in range(max_depth + 1):
            res.append(mp[i])

        return res

    def solve(self , preOrder: List[int], inOrder: List[int]) -> List[int]:
        # write code here
        res = []
        if (len(preOrder) == 0):
            return res
        
        root = self.buildTree(preOrder, 0 ,len(preOrder) - 1, inOrder, 0, len(inOrder) - 1)

        return self.rightSideView(root)
        
        pass
		
		备注一下，需要整理思路，照抄的