一、题目描述
输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
限制:
0 <= 节点个数 <= 5000
二、解题思路
二叉树前序遍历的顺序为:
- 先遍历根节点;
- 随后递归地前序遍历左子树;
- 最后递归地前序遍历右子树。
二叉树中序遍历的顺序为:
- 先递归地中序遍历左子树;
- 随后遍历根节点;
- 最后递归地中序遍历右子树。
通过上述观察,我们可以发现:
- 前序遍历序列的 第一个元素 是根。
- 在中序遍历序列中,根的两边 分别是左子树和右子树的中序序列。
- 通过中序序列的根的两边的左右子树的各自的 长度 可以将前序序列除根以外的后面所有元素划分为 两个前序的左、右子树序列。这两个前序的左、右子树序列同样遵循上述三点规律。
在重建二叉树时,我们可以自底向上递归地构建二叉树。
三、我的题解
我们用三个函数实现上述三个功能:
take
函数执行第一步,取出根元素。并返回剩余元素组成的切片。div_mid
函数执行第二步,将中序遍历序列按根的两边划分为左子树和右子树。div_two
执行第三步,按左右子树的各自的 长度 可以将前序序列除根以外的后面所有元素划分为 两个前序的左、右子树序列。
然后用 fen
函数将上述三个步骤组合起来。
最后在总函数 buildTree
中实现递归调用。
Go 语言代码:
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder) == 0 && len(inorder) == 0{
return nil
}
// 取 preorder 的第一个值 value,并将 preorder 分成左子树 p1 和右子树 p2 ,将 inorder 分成左子树 i1 和右子树 i2
value, i1, i2, p1, p2 := fen(preorder, inorder)
// 新建节点
newpoint := &TreeNode{Val:value}
// 递归调用
newpoint.Left = buildTree(p1, i1)
newpoint.Right = buildTree(p2, i2)
return newpoint
}
func take(intput []int) (a int, output []int) {
if len(intput) > 0{
output = intput[1:]
return intput[0], output
}else{
return 0, intput
}
}
// 将切片以值 a 为分界线,划分为左右两部分
func div_mid(a int, input []int) (div1 []int, div2 []int){
if len(input) > 0 {
for i, j := range input {
if j == a {
div1 := input[:i]
div2 := input[i+1:]
return div1, div2
}
}
}else{
return nil, nil
}
return nil, nil
}
// 将切片划分为两部分,第一部分长度为 len1,剩下的为第二部分
func div_two(len1 int, intput []int) (div1 []int, div2 []int){
if len1 < len(intput){
div1 := intput[:len1]
div2 := intput[len1:]
return div1, div2
}else if len1 == len(intput){
return intput, []int{}
}else{
return nil, nil
}
}
// 将 preorder 分成左子树p1和右子树p2,将 inorder 分成左子树i1和右子树i2
func fen(preorder []int,inorder []int) (int, []int, []int, []int, []int){
value, preorder := take(preorder)
i1,i2 := div_mid(value, inorder)
p1,p2 := div_two(len(i1), preorder)
return value, i1, i2, p1, p2
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之家整理,本文链接:https://www.bmabk.com/index.php/post/118929.html