视图"/>
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
更多推荐
NC136 输出二叉树的右视图
发布评论