当前位置：首页 > backend >正文

可视化图解算法38：重建二叉树

backend 2025/7/3 8:48:40

1. 题目

描述

给定节点数为 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 ≤2000，节点的值 -10000≤val≤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}

2. 解题思路

本题需要通过二叉树的前序遍历结果与中序遍历结果构建出二叉树来，因此需要先了解二叉树前序遍历与中序遍历的规律：

1）前序遍历，根节点是在最前面；

2）中序遍历，根节点是在中间位置（即：根节点元素前面的为左子树，后面的为右子树）。

了解了规律，再来看思路：

根据思路，对应的递推公式如下：

有了递推公式，就可以很方便的写出代码。

如果文字描述的不太清楚，你可以参考视频的详细讲解。

Python版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1372249
Java版本：数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1367357
Golang版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364782

3. 编码实现

核心代码如下：

type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param preOrder int整型一维数组* @param vinOrder int整型一维数组* @return TreeNode类*/
func reConstructBinaryTree(pre []int, vin []int) *TreeNode {// write code here// 2. 递归终止条件（pre、vin长度一样，只需要判断一个即可）if len(pre) == 0 {return nil}// 1. 问题分解（递推公式）// 1.1 根节点（前序遍历的第一个值）root := &TreeNode{Val: pre[0]}// 1.2 根节点在中序遍历中的位置index := getIndex(vin, pre[0])// 1.3 以根节点索引为分割线，将数组pre、vin分为左右两部分root.Left = reConstructBinaryTree(pre[1:index+1], vin[:index])   //左部分构成左子树（切片截取：左闭右开）root.Right = reConstructBinaryTree(pre[index+1:], vin[index+1:]) //右部分构成右子树return root
}func getIndex(vin []int, v int) int {for index, data := range vin {if data == v {return index //根据题目：pre 和 vin 均无重复元素，因此找到元素即可返回}}return 0
}

具体完整代码你可以参考下面视频的详细讲解。

Python版本：数据结构笔试面试算法-Python语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Python语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1372249
Java版本：数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1367357
Golang版本：数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1364782