树是一种重要的数据结构,终于开始刷树了😊
今天刷的是二叉树的三种基本变量–二叉树的前序遍历、二叉树的中序遍历和二叉树的后序遍历。三种遍历大同小异,只是输出元素的位置不一样,就不过多赘述了。

三种遍历

代码和leetcode上的不太一样,但稍微改动一下就能提交了。代码如下:

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
package main

import (
"fmt"
)

type nodeType interface{}

type TreeNode struct {
value nodeType
left, right *TreeNode
}

// BinaryTree proOrder function
func (t *TreeNode) preOrder() {
if t == nil || t.value == nil {
return
}
fmt.Println(t.value)
t.left.preOrder()
t.right.preOrder()
}

// binaryTree inOrder function
func (t *TreeNode) inOrder() {
if t == nil || t.value == nil {
return
}
t.left.inOrder()
fmt.Println(t.value)
t.right.inOrder()
}

// BinaryTree postOrder function
func (t *TreeNode) postOrder() {
if t == nil || t.value == nil {
return
}
t.left.postOrder()
t.right.postOrder()
fmt.Println(t.value)

}

func newTree(inputList *[]nodeType) *TreeNode {
if len(*inputList) == 0 || inputList == nil {
return nil
}

data := (*inputList)[0]
*inputList = (*inputList)[1:]

if data == nil {
return nil
}

node := &TreeNode{data, nil, nil}
node.left = newTree(inputList)
node.right = newTree(inputList)
return node
}

func main() {
inputList := []nodeType{3, 2, 9, nil, nil, 10, nil, nil, 8, nil, 4}
root := newTree(&inputList)
fmt.Println("res", root.left.right.value)
fmt.Println("前序遍历")
root.preOrder()
fmt.Println("中序遍历")
root.inOrder()
fmt.Println("后续遍历")
root.postOrder()
}