前言
面试中有很多有关二叉树的题目,且需要手动建树,这里记录一下如何用Golang来快速构建一个二叉树。
代码实现
我们知道二叉树可以扁平化到数组中,当前节点的左右子节点的在数组中的下标可以表示为
leftIndex := currIndex * 2 + 1
rightIndex := currIndex * 2 + 2
其中currIndex表示当前节点在数组中的下标,基于此我们可以构建二叉树。
Node节点数据结构
type Node struct {
Val int
Left, Right *Node
}
buildTree方法
// buildTree 构建树并且返回树的头节点
// arr 树节点的扁平化数组,其中-1表示空节点
// index 当前节点在数组中的下标
// n 数组长度
func buildTree(arr []int, index, n int) *Node {
if n == 0 || index >= n || arr[index] == -1 {
return nil
}
return &Node{
Val: arr[index],
Left: buildTree(arr, index*2+1, n),
Right: buildTree(arr, index*2+2, n),
}
}
验证
使用层序遍历输出构建完成的树,来验证一下
func bfs(root *Node) {
if root == nil {
return
}
q := []*Node{root}
for len(q) > 0 {
size := len(q)
for i := 0; i < size; i++ {
node := q[0]
q = q[1:]
fmt.Printf("%v ", node.Val)
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
fmt.Println()
}
}
func main() {
arr := []int{0, 1, 2, 3, 4, -1, 6}
root := buildTree(arr, 0, len(arr))
fmt.Println("---层序---")
bfs(root)
/* 树结构:
0
1 2
3 4 null 6
输出结果:
---层序---
0
1 2
3 4 6
*/
}