韩槑槑

LeetCode 常用结构之 树

字数统计: 363阅读时长: 1 min
2018/12/02 Share

常用的数据结构

LeetCode 刷题的时候有几个常见的数据结构
其中最常用的是 链表
所以我把这两个数据结构单独写了两个包
下面先说的树结构

代码仓库:https://github.com/Han-MeiM/leetCode/tree/master/structure

树结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
package TreeNode

import (
"fmt"
"strconv"
"strings"
)

type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}


// 生成树结构
func CreateTestData(data string) *TreeNode {
if data == "[]" {
return nil
}
data = string([]rune(data)[1 : len(data)-1])
res := strings.Split(data, ",")
length := len(res)
treeNode := make([]*TreeNode, length)
for i := 0; i < length; i++ {
if res[i] != "nil" {
val, err := strconv.Atoi(res[i])
if err != nil {
panic(err)
}
treeNode[i] = &TreeNode{val, nil, nil}
}
}
for i := 0; i < length; i++ {
if treeNode[i] != nil {
leftIndex := i*2 + 1
if leftIndex < length && treeNode[leftIndex] != nil {
treeNode[i].Left = treeNode[leftIndex]
}
rightIndex := leftIndex + 1
if rightIndex < length && treeNode[leftIndex] != nil {
treeNode[i].Right = treeNode[rightIndex]
}
}
}
return treeNode[0]
}

const spce = " "

// 打印树
func Print(root *TreeNode) {
treeNodePrint(root, 0)
}

func treeNodePrint(node *TreeNode, deep int) {
if node == nil {
printSpace(deep)
fmt.Println("#")
return
}
treeNodePrint(node.Right, deep+1)
printSpace(deep)
printNode(node.Val)
treeNodePrint(node.Left, deep+1)
}

func printSpace(count int) {
for i := 0; i < count; i++ {
fmt.Printf(spce)
}
}

func printNode(val int) {
var buffer strings.Builder
temp := strconv.Itoa(val)
buffer.WriteString(temp)
buffer.WriteString("<")
spceNum := len(spce) - buffer.Len()
for i := 0; i < spceNum; i++ {
buffer.WriteString(" ")
}
fmt.Println(buffer.String())
}

使用

1.创建树结构

1
2
// 注意不要有空格
tree := TreeNode.CreateTestData("[1,2,3,4]")

2.打印树结构

1
TreeNode.Print(tree)

3.效果
file


CATALOG
  1. 1. 常用的数据结构
  2. 2. 树结构
  3. 3. 使用