首页 > 试题广场 >

重建二叉树

[编程题]重建二叉树

热度指数：1327089 时间限制：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，点此查看相关信息

算法知识视频讲解

推荐

欲风

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
    	TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
    	return root;
    }
    //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
    private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {
    	
    	if(startPre>endPre||startIn>endIn)
    		return null;
    	TreeNode root=new TreeNode(pre[startPre]);
    	
    	for(int i=startIn;i<=endIn;i++)
    		if(in[i]==pre[startPre]){
    			root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
    			root.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
                      break;
    		}
    			
    	return root;
    }
}

编辑于 2018-03-21 14:58:42 回复(255)

Python

不愿吃饼的三文鱼很调皮

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if not pre&nbs***bsp;not tin: return None
        mydict = {k:v for v,k in enumerate(tin)}
        return self.helper(pre, 0, len(pre)-1, tin, 0, len(tin)-1, mydict)
    
    def helper(self, pre, prebegin, preend, mid, midbegin, midend, mydict):
        # 判空
        if prebegin > preend&nbs***bsp;midbegin>midend: return
        # 根节点就是前序序列的第一个节点
        rindex = mydict[pre[prebegin]]
        # 根据序号在中序序列中取根节点
        root = TreeNode(mid[rindex])
        root.left = self.helper(pre, prebegin+1, rindex+prebegin-midbegin, mid, midbegin, rindex-1, mydict)
        root.right = self.helper(pre, rindex+prebegin-midbegin+1, preend, mid, rindex+1, midend, mydict)
        return root

发表于 2021-06-27 10:10:24 回复(0)

Python

牛客541273514号

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if not pre&nbs***bsp;not tin:
            return None
        while tin:
            rootindexintin=tin.index(pre.pop(0))
            root=TreeNode(tin[rootindexintin])
            root.left=self.reConstructBinaryTree(pre,tin[:rootindexintin])
            root.right=self.reConstructBinaryTree(pre,tin[rootindexintin+1:])
            return root
        return Node

发表于 2021-04-11 09:48:52 回复(0)

Python

Xsq30

class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code here
root = TreeNode(pre[0])
index = tin.index(pre[0])
self.recur(root, pre[1: index+1], tin[0: index], pre[index+1:], tin[index+1:])
return root

def recur(self, node, left_pre, left_tin, right_pre, right_tin):
if (not left_pre) and (not right_pre):
return
if left_pre:
node.left = TreeNode(left_pre[0])
index_left = left_tin.index(left_pre[0])
self.recur(node.left, left_pre[1: index_left+1], left_tin[0:index_left],
left_pre[index_left+1:], left_tin[index_left+1:])
if right_pre:
node.right = TreeNode(right_pre[0])
index_right = right_tin.index(right_pre[0])
self.recur(node.right, right_pre[1: index_right+1], right_tin[0:index_right],
right_pre[index_right+1:], right_tin[index_right+1:])

编辑于 2021-02-22 11:40:12 回复(0)

Python

保洁大哥

# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code here
if len(pre)>0 and len(tin)>0:
index = 0
x = TreeNode(pre[0])
for i in range(len(tin)):
if tin[i] == x.val:
index = i
break
x.left = self.reConstructBinaryTree(pre[1:index+1], tin[0:index])
x.right = self.reConstructBinaryTree(pre[index+1:], tin[index+1:])
return x
else:
return None
递归生成即可

发表于 2021-01-26 20:58:28 回复(0)

Python

611的

python实现，递归。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        if(len(pre)==0):
            return None
        else:
            treenode = TreeNode(pre[0])
            idx = tin.index(pre[0])
            pre_left = pre[1:idx+1]
            pre_right = pre[idx+1:]
            tin_left = tin[:idx]
            tin_right = tin[idx+1:]
            treenode.left = self.reConstructBinaryTree(pre_left,tin_left)
            treenode.right = self.reConstructBinaryTree(pre_right,tin_right)
            return treenode

发表于 2021-01-24 11:09:37 回复(0)

Python

路灯灯灯

简单的python解法

1.前序遍历的第一个元素是根节点 root ；
2.在中序遍历中找到该root 的位置，就可以把中序遍历划分为左子树 | 根节点 | 右子树。
3.再根据中序遍历中的左右子树的节点数量，可以把前序遍历划分为根节点 | 左子树 | 右子树

def reConstructBinaryTree(self, pre, tin):
        # write code here
        if not pre: return
        root = TreeNode(pre[0])
        l = tin.index(pre[0])
        root.left = self.reConstructBinaryTree(pre[1:l+1], tin[:l])
        root.right = self.reConstructBinaryTree(pre[l+1:], tin[l+1:])
        return root

发表于 2020-10-13 17:17:33 回复(0)

Python

牛客1349号

python实现，根据先序遍历根左右求出树根结点，再根据中序遍历切割左右子树，使用递归，依次添加左右孩子。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if not pre:
            return pre
        if len(pre) == 1:
            return TreeNode(pre[0])
        root = TreeNode(pre[0])
        temp = tin.index(pre[0])
        left = tin[:temp]
        right = tin[temp+1:]
        if not len(left):
            root.left = None
        else:
            root.left = self.reConstructBinaryTree(pre[1:temp+1], left)
        if not len(right):
            root.right = None
        else:
            root.right = self.reConstructBinaryTree(pre[temp+1:], right)
        return root

发表于 2020-07-26 10:39:02 回复(0)

Python

DDooo

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if len(pre) == 0:
            return None
        if len(pre) == 1:
            return TreeNode(pre[0])
        else:
            flag = TreeNode(pre[0])
            #接下来找左子树的前序遍历和中序遍历，依次递推（依据是前序遍历的根节点+左子树的节点个数之和=中序遍历的左子树+根节点的节点个数之和）
            #且左子树的前序遍历还得在整体的前序遍历中找，左子树的中序遍历还得在整体的中序遍历中找
            flag.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1], tin[0:tin.index(pre[0])])
            #接下来找右子树的前序遍历和中序遍历，依次递推
            #且右子树的前序遍历还得在整体的前序遍历中找，右子树的中序遍历还得在整体的中序遍历中找
            flag.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1:], tin[tin.index(pre[0])+1:])
        return flag

发表于 2020-07-23 09:59:20 回复(0)

Python

生下来就会跑

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        root ,sp = self.fun(0, pre, tin)
        return root
    def fun(self,sp,pre,tin):
        if not tin:return None,sp
        n = tin.index(pre[sp])
        node = TreeNode(pre[sp])
        node.left,sp = self.fun(sp, pre, tin[:n])
        node.right,sp = self.fun(sp, pre, tin[n+1:])
        return node,sp

发表于 2020-06-23 22:04:49 回复(0)

Python

WilliamYr

利用递归方法。前序遍历可以确定根节点，中序遍历可以确定左、右子树。

树结点已经定义好，可以直接调用TreeNode，树可以用根节点root来表示，即最后返回root。

左子树root.left

右子树root.right

def reConstructBinaryTree(self,pre,tin):
    '''pre:前序遍历的序列，tin：中序遍历的序列'''
    if len(pre)==0:
        return None
    elif len(pre)==1:
        return TreeNode(pre[0])
    root=TreeNode(pre[0])
    tin_left=tin[0:tin.index(pre[0])]
    tin_right=tin[tin.index(pre[0])+1:]
    pre_left=pre[1:tin.index(pre[0])+1]
    pre_right=pre[tin.index(pre[0])+1:]
    root_left=self.reConstructBinaryTree(pre_left,tin_left)
    root_right=self.reConstructBinaryTree(pre_right,tin_right)
    return root

编辑于 2020-03-27 13:13:05 回复(0)

Python

朝夕_

class Solution:
    def reConstructBinaryTree(self, pre, tin):
        if not pre:
            return
        elif len(pre) == 1:
            return TreeNode(pre[0])
        else:
            root = TreeNode(pre[0])
            tinL = tin[:tin.index(pre[0])]
            tinR = tin[tin.index(pre[0])+1:]
            root.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],tinL)
            root.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1:],tinR)
            return root

发表于 2020-03-01 22:13:44 回复(0)

Python

DelPotro

Python解法：

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        if not pre or not tin:
            return None
        root = TreeNode(pre[0])
        index = tin.index(root.val)
        root.left = self.reConstructBinaryTree(pre[1:index+1], tin[:index])
        root.right = self.reConstructBinaryTree(pre[index+1:], tin[index+1:])
        return root

编辑于 2019-12-17 16:59:14 回复(0)

Python

天山剑客

# 解题思路：先序序列里的节点把中序序列分为两部分
# 左侧对应左子树，右侧对应右子树，按照对应关系递归即可
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if not pre:
            return None

        if not tin:
            return None

        n = pre.pop(0)
        rt = TreeNode(n)
        if n in tin:
            k = tin.index(n)

            rt.left = self.reConstructBinaryTree(pre, tin[0: k])
            rt.right = self.reConstructBinaryTree(pre, tin[k + 1:])

        return rt

发表于 2019-12-04 19:14:41 回复(0)

Python

黄沙遮天

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if len(pre)!=len(tin):
            return None
        if len(pre)!=0:
            cur=pre[0]
            i=tin.index(cur)
            node1=TreeNode(cur)
            node1.left=self.reConstructBinaryTree(pre[1:i+1],tin[:i])
            node1.right=self.reConstructBinaryTree(pre[i+1:],tin[i+1:])
            return node1
这道题就是一个递归的简单应用，首先从前序遍历的首位置拿到根，然后利用根将此时tin一分为二，分别进行左右
子树的递归，记住有一个不太一样的就是左子树的pre的第一个元素不能包含在内，因为它是根

发表于 2019-11-14 16:12:04 回复(0)

Python

秋水中的鱼

递归方式求解,自顶而下，终止条件为pre中只剩一个节点。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if not pre:
            return
        if len(pre)==1:
            return TreeNode(pre[0])
        res=TreeNode(pre[0])
        left=tin[:tin.index(pre[0])]
        right=tin[tin.index(pre[0])+1:]
        res.left=self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],left)
        res.right=self.reConstructBinaryTree(pre[tin.index(pre[0])+1:],right)
        return res

发表于 2019-10-14 19:31:51 回复(0)

Python

贾志统

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if len(pre) == 0:
            return None
        if len(pre) == 1:
            return TreeNode(pre[0])
        flag = TreeNode(pre[0])
        i = tin.index(pre[0])
        flag.left = self.reConstructBinaryTree(pre[1:i+1], tin[0:i])
        flag.right = self.reConstructBinaryTree(pre[i+1:], tin[i+1:])
        return flag

发表于 2019-08-30 19:52:27 回复(0)

Python

已注销

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        l = len(pre)
        if l == 1:
            return TreeNode(pre[0])
        else:
            p = TreeNode(pre[0])
            for j in range(l):
                if tin[j] == pre[0]:
                    if j == 0:
                        p.right = self.reConstructBinaryTree(pre[1:], tin[j+1:])
                    elif j == l-1:
                        p.left = self.reConstructBinaryTree(pre[1:], tin[:j])
                    else:
                        p.left = self.reConstructBinaryTree(pre[1:j+1], tin[:j])
                        p.right = self.reConstructBinaryTree(pre[j+1:], tin[j+1:])
            return p

发表于 2019-08-15 16:08:32 回复(0)

Python

&pipemm

发表于 2019-08-02 17:29:49 回复(0)

Python

不多不多，offer就要五个

# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code here
if not pre:
return None
root = TreeNode(pre[0])
index = tin.index(root.val)
root.left = self.reConstructBinaryTree(pre[1:1+index], tin[:index])
root.right = self.reConstructBinaryTree(pre[1+index:], tin[index+1:])

return root
'''
if len(pre)==0:
return None
root = TreeNode(pre[0])
if len(pre)==1:
return root
root.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1], tin[:tin.index(pre[0])])
root.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1:], tin[tin.index(pre[0])+1:])
return root
'''

发表于 2019-07-07 11:07:43 回复(0)

Python

没有offer心好慌

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if len(pre)==0:
            return None
        node = TreeNode(pre[0])
        left_tin = tin[:tin.index(pre[0])]
        left_pre = pre[1:len(left_tin)+1]
        right_tin = tin[tin.index(pre[0])+1:]
        right_pre = pre[len(left_pre)+1:]
        node.left = self.reConstructBinaryTree(left_pre,left_tin)
        node.right = self.reConstructBinaryTree(right_pre,right_tin)
        return node

利用递归算法即可求解，取出根节点后，再递归调用，将左子树的前序中序和右子树的前序中序分别传入函数即可。

编辑于 2019-07-05 14:53:40 回复(0)

提交观点

问题信息

数组树 dfs

难度：

82条回答 8279收藏 304838浏览

通过挑战的用户

查看代码

随机昵称都有什...

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，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题