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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 求二叉树的右视图
# @param xianxu int整型一维数组 先序遍历
# @param zhongxu int整型一维数组 中序遍历
# @return int整型一维数组
# 属于一个综合题，先按照中序先序建立二叉树，再输出右视图
# 自己定义的二叉树结构
class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = None
        self.right = None

class Solution:
    def solve(self , xianxu: List[int], zhongxu: List[int]) -> List[int]:
        # write code here
        if not xianxu: # 空树
            return []

        def rebuild(firstorder, midorder): # 重构二叉树的函数
            if not firstorder:
                return
            root = TreeNode(firstorder[0]) # 构建树节点
            cur_idx = midorder.index(root.val)
            mid_left = midorder[:cur_idx]
            mid_right = midorder[cur_idx+1:]
            length = len(mid_left)
            first_left = firstorder[1:1+length]
            first_right = firstorder[length+1:] # 划分左右子树
            root.left = rebuild(first_left, mid_left) # 递归生成左子树
            root.right = rebuild(first_right, mid_right) # 递归生成右子
            return root
        
        root = rebuild(xianxu, zhongxu) # 重构完成

        from collections import deque
        res = [] # 接下来就是正常的层序遍历，保留每一层最后一个节点就可以
        DQ = deque([root])
        L = 1
        while DQ:
            for i in range(L):
                cur = DQ.popleft()
                if i == L -1:
                    res.append(cur.val)
                if cur.left:
                    DQ.append(cur.left)
                if cur.right:
                    DQ.append(cur.right)
            L = len(DQ)

        return res