思路： 1.前序遍历的第一个节点是二叉树的根节点 2.中序遍历中，根节点左边是左子树，右边是右子树 3.理清思绪递归实现即可
func buildTree(preorder []int, inorder []int) *TreeNode {
//结束条件，最下面的叶子节点时结束
if len(preorder) == 0 {
return nil
}
//根据前序遍历的性质在中序遍历中找到根节点的位置
var i = 0
for i < len(preorder) && preorder[0] != inorder[i] {
i++
}
//递归左子树
l := buildTree(preorder[1:i+1], inorder[:i])
//递归右子树
r := buildTree(preorder[i+1:], inorder[i+1:])
return &TreeNode{
Val: preorder[0],
Left: l,
Right: r,
}
}
测试代码：
package main
import "fmt"
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func main() {
//var preorder = []int{3,9,20,15,7}
//var inorder = []int {9,3,15,20,7}
var preorder = []int{1,2,4,8,5,9,3,6,7,10}
var inorder = []int{4,8,2,9,5,1,6,3,7,10}
root := buildTree(preorder,inorder)
//前序遍历
//printVLRTree(root)
//中序遍历
//printLDRTree(root)
//后序遍历
printLRDTree(root)
}
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder) == 0 {
return nil
}
var i = 0
for i < len(preorder) && preorder[0] != inorder[i] {
i++
}
//fmt.Println(preorder,inorder,i)
l := buildTree(preorder[1:i+1], inorder[:i])
r := buildTree(preorder[i+1:], inorder[i+1:])
return &TreeNode{
Val: preorder[0],
Left: l,
Right: r,
}
}
//前序遍历
func printVLRTree(root *TreeNode){
if root == nil {
return
}
fmt.Println(root.Val)
printVLRTree(root.Left)
printVLRTree(root.Right)
}
//中序遍历
func printLDRTree(root *TreeNode){
if root == nil {
return
}
printLDRTree(root.Left)
fmt.Println(root.Val)
printLDRTree(root.Right)
}
//后序遍历
func printLRDTree(root *TreeNode){
if root == nil {
return
}
printLRDTree(root.Left)
printLRDTree(root.Right)
fmt.Println(root.Val)
}
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/admin_o1/article/details/111246025
