目的
想输入一个数组，然后构造二叉树
例如数组为[6, 2, 8, 0, 4, 7, 9, -1, -1, 3, 5]
对应的二叉树为：
参考资料
ACM模式数组构建二叉树
重点：如果父节点的数组下标是i，那么它的左孩子下标就是i*2+1，右孩子下标就是i*2+2。文章来源：https://www.toymoban.com/news/detail-690166.html
go代码实现
package main
import "fmt"
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// 根据数组构造二叉树
func constructBinaryTree(nums []int) *TreeNode {
treenode := make([]*TreeNode, len(nums))
for i := 0; i < len(nums); i++ {
var node *TreeNode //如果等于-1的话就是nil
if nums[i] != -1 {
node = &TreeNode{Val: nums[i]}
treenode[i] = node
}
}
for i := 0; i*2+2 < len(nums); i++ {
if treenode[i] != nil {
treenode[i].Left = treenode[i*2+1]
treenode[i].Right = treenode[i*2+2]
}
}
return treenode[0] //root=treenode[0]
}
// 前序遍历-用于验证
func preorderTraversal(root *TreeNode) (res []int) {
var traversal func(node *TreeNode)
traversal = func(node *TreeNode) {
if node == nil {
return
}
res = append(res, node.Val)
traversal(node.Left)
traversal(node.Right)
}
traversal(root)
return res
}
// 中序遍历-用于验证
func inorderTraversal(root *TreeNode) (res []int) {
var traversal func(node *TreeNode)
traversal = func(node *TreeNode) {
if node == nil {
return
}
traversal(node.Left)
res = append(res, node.Val)
traversal(node.Right)
}
traversal(root)
return res
}
// 后序遍历-用于验证
func postorderTraversal(root *TreeNode) (res []int) {
var traversal func(node *TreeNode)
traversal = func(node *TreeNode) {
if node == nil {
return
}
traversal(node.Left)
traversal(node.Right)
res = append(res, node.Val)
}
traversal(root)
return res
}
func main() {
nums := []int{6, 2, 8, 0, 4, 7, 9, -1, -1, 3, 5}
root := constructBinaryTree(nums)
fmt.Println("前序遍历：", preorderTraversal(root))
fmt.Println("中序遍历：", inorderTraversal(root))
fmt.Println("后序遍历：", postorderTraversal(root))
}
输出：文章来源地址https://www.toymoban.com/news/detail-690166.html
前序遍历： [6 2 0 4 3 5 8 7 9]
中序遍历： [0 2 3 4 5 6 7 8 9]
后序遍历： [0 3 5 4 2 7 9 8 6]
到了这里，关于ACM模式数组构建二叉树Go语言实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
