-
Notifications
You must be signed in to change notification settings - Fork 0
/
103.go
70 lines (64 loc) · 1.35 KB
/
103.go
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
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**************DFS 深度优先********************/
func zigzagLevelOrder(root *TreeNode) [][]int {
ans := [][]int{}
dfs(root, 0, &ans)
return ans
}
func dfs(root *TreeNode, depth int, ans *[][]int) {
// dfs终止条件
if root == nil {
return
}
// 当前层还没有集合,先创建集合
if depth >= len(*ans) {
*ans = append(*ans, []int{})
}
if depth & 1 == 0 {
// 顺序插入
(*ans)[depth] = append((*ans)[depth], root.Val)
} else {
// 倒序插入
(*ans)[depth] = append([]int{root.Val}, (*ans)[depth]...)
}
dfs(root.Left, depth +1, ans)
dfs(root.Right, depth +1, ans)
}
/**********BFS 广度优先***********/
func zigzagLevelOrder(root *TreeNode) [][]int {
var res[][]int
if root == nil {
return res
}
queue := make([]*TreeNode,0)
queue = append(queue, root)
isLeftStart := true
for len(queue) > 0 {
l := len(queue)
ans := make([]int,l)
for i := 0; i< l; i++ {
node := queue[i]
if node.Left != nil {
queue = append(queue, nodee.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
if isLeftStart {
ans[i] = node.Val
} else {
ans[l-i-1] = node.Val
}
}
res = append(res, ans)
isLeftStart = !isLeftStart
queue = queue[l:]
}
}