我要招人

去企业版

首页 > 试题广场 >

输出二叉树的右视图

[编程题]输出二叉树的右视图

热度指数：53520 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围： $0 \le n \le 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]内，且保证每个节点的值互不相同。

算法知识视频讲解

摸鱼学大师

发表于 2021-07-24 15:15:27

精华题解思路：题目的主要信息：利用二叉树中序遍历结果及先序遍历结果构建一棵二叉树打印二叉树的右视图，即二叉树每层最右边的结点元素节点值互不相同可以发现解这道题，我们有两个步骤：建树打印右视图首先建树方面，先序遍历是根左右的顺序，中序遍历是左根右的顺序，因为节点值互不相同，我们可以根据展开全文

牛客题解官

发表于 2022-04-22 12:12:58

精华题解题目的主要信息：利用二叉树中序遍历结果及前序遍历结果构建一棵二叉树打印二叉树的右视图，即二叉树每层最右边的节点元素节点值互不相同举一反三：学习完本题的思路你可以解决如下题目： BM40. 重建二叉树 BM38. 在二叉树中找到两个节点的最近公共祖先 BM29. 二叉树中和为某一值的路径展开全文

_LittleBee

发表于 2021-10-19 18:15:50

这题和之前构建二叉树的题其实时一样的，小改动了一下。具体的思路：答案数组的大小其实是对应二叉树的高度，或者说这二叉树有多少层。二叉树每层只能有一个顶点，这个顶点就是二叉树该层最右边的节点我构建二叉树是递归的构建左子树和右子树，这样左子树的最右子节点会被右子树的最右子节点给覆盖掉(前提是该节展开全文

牛客968762647号

发表于 2021-09-23 00:10:59

# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # 求二叉树的右视图 # @param xianxu int整型一维数组先序遍历 # @param zhongxu int整型一维数组中序遍历 # @return int整型一维数组 # class Solutio 展开全文

子夜降晴空

发表于 2021-03-22 21:53:22

class Solution { public: vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) { vector<int> res; 展开全文

changed.

发表于 2021-07-22 15:44:13

题意整理：题目给出一颗二叉树的前序遍历以及中序遍历，要求得到这颗二叉树的右视图。右视图简单的理解，既在树的右侧能够看到的数的第一个元素。更专业的说，即为树的每一层的最右侧元素。方法一：递归+层序遍历核心思想：可以先使用递归，从先序遍历和中序遍历中重构树，再使用层次遍历求出右视图。重构树：对一展开全文

牛客300673134号

发表于 2021-12-08 23:19:22

/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 求二叉树的右视图 * @param xianxu int整型一维数组先序遍历 * @param zhongxu int整型一维数组中序遍历 * @return int整型一维数组 */ func 展开全文

苦学编程30年

发表于 2023-05-22 16:48:03

#include <queue> #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 求二叉树的右视图 * @ 展开全文

Hzu_Lai

发表于 2022-03-14 10:54:17

主要知识点：根据前序+中序递归建树，层次遍历二叉树 import java.util.*; public class Solution { //根据前序+中序遍历重建二叉树 public TreeNode createByPreMid(int[] pre,int[] mid, int ipre,in 展开全文

大厂算法岗必拿下

发表于 2021-09-14 23:45:13

先构建这个树，然后使用分层打印的方式，每次往最终结果放入最后一个元素即可注意索引对齐，有一个方法就是从刚开始大的方式从上到下还有注意结构体声明就是类申明 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # 求二叉树的右视图 # @param xianxu in 展开全文