输出二叉树的右视图

class Solution:
    def solve(self , preOrder: List[int], inOrder: List[int]) -> List[int]:
        if not preOrder:
            return []
        res = [preOrder[0]]
        index = inOrder.index(preOrder[0])
        # 左子树的右视图
        left = self.solve(preOrder[1:index+1], inOrder[:index])
        # 右子树的右视图
        right = self.solve(preOrder[index+1:], inOrder[index+1:])
        # 优先取右子树，剩余取左子树
        return res + right + left[len(right):]

from collections import deque
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def solve(self , preOrder: List[int], inOrder: List[int]) -> List[int]:
        val2idx = {}
        for i in range(len(inOrder)):
            val2idx[inOrder[i]] = i

        def dfs(root_idx, left, right):
            if left > right:
                return None
            # 在 inorder 中的索引
            index = val2idx[preOrder[root_idx]]
            root = TreeNode(inOrder[index])

            root.left = dfs(root_idx+1, left, index-1)
            root.right = dfs(root_idx-left+index+1, index+1, right)

            return root
        # 构建
        root = dfs(0, 0, len(inOrder)-1)

        # BFS 
        res = []
        if not root:
            return res
        q = deque([root])
        while q:
            n = len(q)
            res.append(q[0].val)
            for _ in range(n):
                cur = q.popleft()
                if cur.right:
                    q.append(cur.right)
                if cur.left:
                    q.append(cur.left)
        return res

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 求二叉树的右视图
# @param preOrder int整型一维数组 先序遍历
# @param inOrder int整型一维数组 中序遍历
# @return int整型一维数组
from typing import List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def solve(self , preOrder: List[int], inOrder: List[int]) -> List[int]:
        # write code here
        # 构建二叉树
        root = self.buildTree(preOrder, inOrder)

        # 打印二叉树的右视图
        return self.rightSideView(root)

    def buildTree(self, preOrder: List[int], inOrder: List[int]) -> TreeNode:
        if not preOrder&nbs***bsp;not inOrder:
            return None

        # 根节点的值为前序遍历的第一个元素
        root_val = preOrder[0]
        root = TreeNode(root_val)

        # 在中序遍历中找到根节点的位置
        root_index = inOrder.index(root_val)

        # 构建左子树
        left_preOrder = preOrder[1:root_index+1]
        left_inOrder = inOrder[:root_index]
        root.left = self.buildTree(left_preOrder, left_inOrder)

        # 构建右子树
        right_preOrder = preOrder[root_index+1:]
        right_inOrder = inOrder[root_index+1:]
        root.right = self.buildTree(right_preOrder, right_inOrder)

        return root

    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root:
            return []

        result = []
        queue = [root]

        while queue:
            level_size = len(queue)

            # 遍历当前层级的节点
            for i in range(level_size):
                node = queue.pop(0)

                # 记录最右边的节点值
                if i == level_size - 1:
                    result.append(node.val)

                # 将下一层级的节点加入队列
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return result

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 求二叉树的右视图
# @param xianxu int整型一维数组 先序遍历
# @param zhongxu int整型一维数组 中序遍历
# @return int整型一维数组
#
class Solution:
    def recure(self, pre: List[int], vin: List[int], start: int, end: int) -> TreeNode:
        if start == end:
            return None
        mid, idx = -1, start
        while mid == -1:
            for i in range(start, end):
                if vin[i] == pre[idx]:
                    mid = i
            idx = idx + 1
        root = TreeNode(vin[mid])
        left = self.recure(pre[1:], vin, start, mid)
        right = self.recure(pre, vin, mid + 1, end)
        root.left = left
        root.right = right
        return root

    def solve(self , xianxu: List[int], zhongxu: List[int]) -> List[int]:
        node = self.recure(xianxu, zhongxu, 0, len(zhongxu))
        tmp = [node]
        ret = []
        next = []
        while tmp:
            cur = tmp.pop(0)
            left, right = cur.left, cur.right
            if left:
                next.append(left)
            if right:
                next.append(right)
            if not tmp:
                ret.append(cur.val)
                tmp = next
                next = []
        return ret

先把树构建出来，在通过队列取出每层的最后一个节点的值
时间复杂度：O(n) 空间复杂度：O(n)

class Solution:
    def tree(self, pre, vin):
        if not pre:
            return None
        root = TreeNode(pre[0])
        tem = vin.index(pre[0])
        root.left = self.tree(pre[1:tem+1], vin[:tem])
        root.right = self.tree(pre[tem+1:], vin[tem+1:])
        return root
    def solve(self , pre: List[int], vin: List[int]) -> List[int]:
        res = []
        root = self.tree(pre, vin)
        q = [root]
        while q:
            n = len(q)
            for i in range(n):
                cur = q.pop(0)
                if i == n-1:
                    res.append(cur.val)
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
        return res