NC136 输出二叉树的右视图

视图"/>

NC136 输出二叉树的右视图

BM41 输出二叉树的右视图

描述

请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图

数据范围： 0≤n≤10000
要求： 空间复杂度 O(n)，时间复杂度 O(n)

如输入[1,2,4,5,3],[4,2,5,1,3]时，通过前序遍历的结果[1,2,4,5,3]和中序遍历的结果[4,2,5,1,3]可重建出以下二叉树：

所以对应的输出为[1,3,5]。

示例1

输入：

[1,2,4,5,3],[4,2,5,1,3]

返回值：

[1,3,5]

备注：

二叉树每个节点的值在区间[1,10000]内，且保证每个节点的值互不相同。

解题思路：

哈希表优化的递归建树+层次遍历

LeetCode 105 从前序与中序遍历序列构造二叉树 NC12 重建二叉树_麦格芬230的博客-CSDN博客

LeetCode 199 二叉树的右视图_麦格芬230的博客-CSDN博客

Python代码：

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 求二叉树的右视图
# @param xianxu int整型一维数组 先序遍历
# @param zhongxu int整型一维数组 中序遍历
# @return int整型一维数组
#
from collections import dequeclass Solution:def buildTree(self, preorder, inorder):if not preorder or not inorder:return Noneroot_val = preorder[0]root = TreeNode(root_val)inorder_root_index = inorder.index(root_val)root.left = self.buildTree(preorder[1: inorder_root_index + 1], inorder[:inorder_root_index])root.right = self.buildTree(preorder[inorder_root_index + 1:], inorder[inorder_root_index + 1:])return rootdef solve(self , xianxu: List[int], zhongxu: List[int]) -> List[int]:# write code hereroot = self.buildTree(xianxu, zhongxu)if not root:return Noneres = []Q = deque()Q.append(root)while Q:for _ in range(len(Q)):node = Q.popleft()if node.left:Q.append(node.left)if node.right:Q.append(node.right)res.append(node.val)return res