-
Notifications
You must be signed in to change notification settings - Fork 0
/
verticalTraversal.go
53 lines (51 loc) · 1.19 KB
/
verticalTraversal.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
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func verticalTraversal(root *TreeNode) [][]int {
col:= 0
minCol:= 0
maxCol:= 0
vert:=make(map[int][]int)
hor:=make(map[int][]int)
q:=[]*TreeNode{root}
c:=[]int{col}
cur:=root
for len(q)>0{
n:=len(q)
for i:=0;i<n;i++{
cur,q = q[0],q[1:]
col,c = c[0],c[1:]
if col<minCol {
minCol = col
}
if col>maxCol {
maxCol = col
}
curCol:=col
hor[col] = append(hor[col],cur.Val)
if cur.Left!=nil {
q = append(q,cur.Left)
c = append(c,curCol-1)
}
if cur.Right!=nil {
q = append(q,cur.Right)
c = append(c,curCol+1)
}
}
for i:=minCol;i<=maxCol;i++{
sort.Ints(hor[i])
vert[i] = append(vert[i],hor[i]...)
hor[i] = []int{}
}
}
ans:=[][]int{}
for i:=minCol;i<=maxCol;i++{
ans = append(ans,vert[i])
}
return ans
}