0%

20210306学习记录

2021-03-06 学习记录

今天的学习内容:

  1. 数据结构:树-二叉树
  2. Leetcode刷题:#589 N叉树的前序遍历

1. 数据结构:树-二叉树

二叉树是日常算法中最常用的树,它有很多很优秀的性质。

  1. 二叉树的第i层至多有2^(i-1)个节点
  2. 深度为k的二叉树最多有(2^k)-1个节点
  3. 若二叉树的叶子节点个数为m,度为2的节点树为n,则m=n+1
  4. 具有n个节点的完全二叉树的深度为[log(2,n)]-1,其中[n]表示不超过n的最大整数,log(m,n)表示以m为底n的对数

二叉树这里不需要考虑并发的问题,单棵树的创建不存在多个线程同时创建的问题,二叉树的遍历不存在对节点值的修改,也不存在并发同步问题。

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
package main

import (
"fmt"
"reflect"
)

//BinaryTree the binary tree structure
type BinaryTree struct {
val interface{}
left *BinaryTree
right *BinaryTree
}

// CreateAnyTypeSlice converse interface{} to slice
func CreateAnyTypeSlice(slice interface{}) ([]interface{}, bool) {
val, ok := isSlice(slice)
if !ok {
return nil, false
}

sliceLen := val.Len()

out := make([]interface{}, sliceLen)

for i := 0; i < sliceLen; i++ {
out[i] = val.Index(i).Interface()
}

return out, true
}

func isSlice(slice interface{}) (val reflect.Value, ok bool) {
val = reflect.ValueOf(slice)

if val.Kind() == reflect.Slice {
ok = true
}

return
}

// CreateByPreOrderSequence create a binary tree by a preorder sequence(which contains node and nil, nil means an empty subtree)
func CreateByPreOrderSequence(arr interface{}) *BinaryTree {
slice, ok := CreateAnyTypeSlice(arr)
if !ok {
fmt.Errorf("not a slice")
return nil
}
if len(slice) == 0 {
return new(BinaryTree)
}

var create func([]interface{}, *int) *BinaryTree
create = func(slice []interface{}, flag *int) *BinaryTree {
if *flag < len(slice)-1 {
*flag = *flag + 1
}
if slice[*flag] == nil {
return nil
}
node := new(BinaryTree)
node.val = slice[*flag]
node.left = create(slice, flag)
node.right = create(slice, flag)

return node
}

flag := -1
binaryTree := create(slice, &flag)

// fmt.Println(binaryTree.TraversePreOrder())
return binaryTree
}

// TraversePreOrder traverse in preorder sequence
func (binaryTree *BinaryTree) TraversePreOrder() interface{} {

var traverse func(root *BinaryTree)
var res []interface{}
traverse = func(root *BinaryTree) {
if root == nil {
return
}
res = append(res, root.val)
traverse(root.left)
traverse(root.right)
}

traverse(binaryTree)
return res
}

// TraverseInOrder traverse in inorder sequence
func (binaryTree *BinaryTree) TraverseInOrder() interface{} {
var traverse func(root *BinaryTree)
var res []interface{}
traverse = func(root *BinaryTree) {
if root == nil {
return
}

traverse(root.left)
res = append(res, root.val)
traverse(root.right)
}

traverse(binaryTree)
return res
}

// TraversePostOrder traverse in postorder sequence
func (binaryTree *BinaryTree) TraversePostOrder() interface{} {

var traverse func(root *BinaryTree)
var res []interface{}
traverse = func(root *BinaryTree) {
if root == nil {
return
}
traverse(root.left)
traverse(root.right)
res = append(res, root.val)
}

traverse(binaryTree)
return res
}

出现的问题主要有:

  1. 创建树的函数中,匿名函数的写法一开始存在一些问题,一开始我的写法如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func CreateByPreOrderSequence(arr interface{}) *BinaryTree {
slice, ok := CreateAnyTypeSlice(arr)

// ... 边界检查

// var create func([]interface{}, *int) *BinaryTree
create := func(slice []interface{}, flag *int) *BinaryTree {
if *flag < len(slice)-1 {
*flag = *flag + 1
}
if slice[*flag] == nil {
return nil
}
node := new(BinaryTree)
node.val = slice[*flag]
node.left = create(slice, flag)
node.right = create(slice, flag)

return node
}

// ...
}

但是这样的话内部的traverse()函数将被认为是未定义的,这里必须先声明函数,然后再重新赋值函数实现:

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
func CreateByPreOrderSequence(arr interface{}) *BinaryTree {
slice, ok := CreateAnyTypeSlice(arr)
// ... 边界检查

var create func([]interface{}, *int) *BinaryTree
create = func(slice []interface{}, flag *int) *BinaryTree {
if *flag < len(slice)-1 {
*flag = *flag + 1
}
if slice[*flag] == nil {
return nil
}
node := new(BinaryTree)
node.val = slice[*flag]
node.left = create(slice, flag)
node.right = create(slice, flag)

return node
}

flag := -1
binaryTree := create(slice, &flag)

return binaryTree
}

且这里由于数组在每次遍历每次递归调用都要加一,所以这里需要传入指针实现修改。

这里还存在一个未解决的问题:如果我们不是采取这种函数的结构,而是将这个函数声明为BinaryTree结构的一个方法,即func (binaryTree *BinaryTree) CreateByPreOrderSequence(arr interface{}) error,其他部分不变,最后返回nil,那么最终binaryTree的值在这个函数内被成功修改,但是main函数中的binaryTree依然是nil。

1
2
3
4
5
6
7
8
9
10
11
12
13
func (binaryTree *BinaryTree) CreateByPreOrderSequence(arr interface{}) error {
// ... 同上

var create func([]interface{}, *int) *BinaryTree
create = func(slice []interface{}, flag *int) *BinaryTree {
// ... 同上
}

flag := -1
binaryTree := create(slice, &flag)

return nil
}

初步猜测是binaryTree的值是create函数返回地址处的值,但是main函数中的binaryTree依然指向这个变量new的时候分配的内存空间的地址,这俩地址并不相同,导致main函数中无法读取binaryTree的值,结果返回nil。

2. Leetcode刷题

#589 N叉树的前序遍历

这个题比较简单,遍历n叉树,这里可以使用递归法和非递归法,先是递归法的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func preorder(root *Node) []int {
var res []int
if root == nil {
return res
}

var traverse func(*Node)
traverse = func(root *Node) {
if root == nil {
return
}
res = append(res, root.Val)
for _, child := range root.Children {
traverse(child)
}
}

traverse(root)
return res
}

然后是非递归法,参考二叉树前序遍历的非递归法,我们维护一个栈,每次遍历根节点后将其出栈,随后其所有子节点入栈。这里需要前序遍历,我们需要将每个根节点的所有子节点逆序入栈,这样才能保证每次即将遍历的下一个节点刚好在栈顶的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func preorder(root *Node) []int {
var res []int
var stack []*Node
if root == nil {
return res
}
stack = append(stack, root)

for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = append(res, node.Val)

for i := len(node.Children)-1; i >= 0; i-- {
stack = append(stack, node.Children[i])
}
}

return res
}