我要招人

去企业版

首页 > 试题广场 >

重建二叉树

[编程题]重建二叉树

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

给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。

提示:

1.vin.length == pre.length

2.pre 和 vin 均无重复元素

3.vin出现的元素均出现在 pre里

4.只需要返回根结点，系统会自动输出整颗树做答案对比

数据范围： $n \le 2000$ ，节点的值 $-10000 \le val \le 10000$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

示例1

输入

[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]

输出

{1,2,3,4,#,5,6,#,7,#,#,8}

说明

返回根节点，系统会输出整颗二叉树对比结果，重建结果如题面图示

示例2

输入

[1],[1]

输出

{1}

示例3

输入

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

输出

{1,2,5,3,4,6,7}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Maokt

发表于 2021-06-30 10:38:29

精华题解算法思想一：递归解题思路：二叉树的前序遍历：根左右；中序遍历：左根右由前序遍历知道根节点之后，能在中序遍历上划分出左子树和右子树。分别对中序遍历的左右子树递归进行这一过程即可建树。图解：代码展示： Python版本 class&nb 展开全文

牛客题解官

发表于 2022-04-22 12:11:53

精华题解题目的主要信息：根据二叉树的前序遍历序列和中序遍历序列，重建该二叉树，并返回根节点两个遍历都没有重复的元素举一反三：学习完本题的思路你可以解决如下题目： BM41. 输出二叉树的右视图方法一：递归（推荐使用）知识点：二叉树递归递归是一个过程或函数在其定义或说明中有直接或间接调用自展开全文

如也201810022128875

发表于 2021-07-18 13:29:05

精华题解题目描述给定某二叉树的前序遍历和中序遍历，请重建出该二叉树并返回它的头结点。方法一：递归解题思路前序遍历的第一个节点就是这颗树的根节点。在中序遍历中，找到这个根节点，这个根节点的左边元素就是它的左子树上的元素，这个根节点的右边元素就是它的右子树上的元素。把范围划分好，直到范围上只有一个展开全文

牛一霸

发表于 2021-07-05 23:40:33

精华题解题目：重建二叉树描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。示例1：输入：[1,2,3 展开全文

江南好___

发表于 2021-07-15 18:54:02

精华题解描述题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。示例输入：[1,2,3,4,5,6,7],[ 展开全文

叫我皮卡丘

发表于 2019-08-09 13:16:35

【剑指offer】重建二叉树 --Java实现递归构建二叉树 1. 分析根据中序遍历和前序遍历可以确定二叉树，具体过程为：根据前序序列第一个结点确定根结点根据根结点在中序序列中的位置分割出左右两个子序列对左子树和右子树分别递归使用同样的方法继续分解例如：前序序列{1,2,4,7,3, 展开全文

Ariser.cn

发表于 2019-08-19 15:58:38

前序加中序序列，分解过程图示如下（王道数据结构P120）思路：由先序序列第一个pre[0]在中序序列中找到根节点位置gen 以gen为中心遍历 0~gen左子树子中序序列：0~gen-1，放入vin_left[] 子先序序列：1~gen放入pre_left[]，+1可以看图，因为头部有根节点展开全文

牛客题解官

发表于 2020-05-29 14:41:25

描述这道题综合考察了对二叉树的前序，中序遍历算法的理解，和根据数组建立二叉树的代码考察以及对递归代码的理解与运用。题目难度：三星考察知识：树，递归题解本题解是初学算法的对象，一步步从不会到会的详细讲解。方法：递归算法前置知识：二叉树的前序遍历：根左右二叉树的中序遍历：左根右二叉树的的后展开全文

千川星河技术版

发表于 2019-08-23 09:44:05

关键是：利用前序序列根节点在前找到根节点，用根节点去中序序列划分成两部分，左部分是左子树，右部分是右子树。再利用子树长度去前序序列把前序序列中的左右子树找出来，同时可以找出根节点。递归进行此步骤，如果子树长度为0，则不需要生成子问题。 class TreeNode { int val; 展开全文

道阻且长z

发表于 2019-09-03 17:13:14

思路：前序遍历：根→左→右中序遍历：左→根→右由前序遍历序列pre={1,2,4,7,3,5,6,8}可知根结点是1；则在中序遍历序列in={4,7,2,1,5,3,8,6}中找到1，便可知1所在位置的左侧是左子树,1所在位置的右侧是右子树；递归调用：将左子树和右子树分别看成一颗树，将其前展开全文

Oh~Sunny

发表于 2019-12-28 20:12:27

class Solution: # 返回构造的TreeNode根节点 def reConstructBinaryTree(self, pre, tin): # write code here if len(pre) == 1: 展开全文

心谭

发表于 2019-12-21 23:20:31

【JavaScript】-重建二叉树-剑指offer 题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。展开全文

代码随想录

发表于 2021-03-09 15:32:13

相信很多小伙伴刷题的时候面对力扣上近两千道题目，感觉无从下手，我花费半年时间整理了Github项目：leetcode刷题攻略。里面有100多道经典算法题目刷题顺序、配有40w字的详细图解，常用算法模板总结，以及难点视频讲解，按照list一道一道刷就可以了！star支持一波吧！思路首先回忆一下展开全文

数据结构和算法

发表于 2021-08-03 15:04:27

问题分析做这题之前我们先来看一下树的几种遍历顺序。先序遍历：根节点→左子树→右子树。中序遍历：左子树→根节点→右子树。后续遍历：左子树→右子树→根节点。其实也很好记，他是根据根节点遍历的顺序来定义的，比如先遍历根节点就是先序遍历，中间遍历根节点就是中序遍历，最后遍历根节点就是后续遍历，至于展开全文

把牛妹带回家

发表于 2019-07-26 15:40:43

思路：递归并正确分割前序和中序序列前序分割为左子树和右子树，左子树的开头是第二个数，中间包含节点的数量为中序从0到根节点的数量所以是pre[1:tin.index(pre[0])+1]右子树是剩下的部分同理，中序左子树是从左边到根节点的部分，tin[:tin.index(pre[0])] 递归展开全文

问题信息

数组树 dfs

难度：

2463条回答 8101收藏 301214浏览

通过挑战的用户

查看代码

随机昵称都有什...

2023-03-13 18:02:13
松林子木

2023-03-09 12:04:02
Elastic...

2023-02-03 15:34:42
冷艳的迪恩在攒经验

2022-10-25 22:16:24
灰度值为零

2022-09-20 11:25:19

重建二叉树

输入

输出

说明

输入

输出

输入

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题