-
Notifications
You must be signed in to change notification settings - Fork 1
/
flatten.go
78 lines (70 loc) · 1.39 KB
/
flatten.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
71
72
73
74
75
76
77
78
package flatten
import (
"github.com/catorpilor/leetcode/utils"
)
func Flatten(root *utils.TreeNode) []int {
if root == nil {
return nil
}
q := utils.NewQueue()
preOrder(root, q)
_ = q.Pull()
root.Left = nil
prev := root
for !q.IsEmpty() {
n := q.Pull().(*utils.TreeNode)
// fmt.Println(n.Val)
prev.Right = n
n.Left = nil
prev = n
}
return utils.LevelOrderTravesal(root)
// return ret
}
func preOrder(node *utils.TreeNode, q *utils.Queue) {
if node == nil {
return
}
q.Enroll(node)
preOrder(node.Left, q)
preOrder(node.Right, q)
}
func Flatten2(root *utils.TreeNode) []int {
if root == nil {
return nil
}
// bottom up recursion
_ = reversedPreOrder(root, nil)
return utils.LevelOrderTravesal(root)
}
func reversedPreOrder(node, prev *utils.TreeNode) *utils.TreeNode {
if node == nil {
return prev
}
prev = reversedPreOrder(node.Right, prev)
prev = reversedPreOrder(node.Left, prev)
node.Right = prev
node.Left = nil
prev = node
return prev
}
func Flatten3(root *utils.TreeNode) []int {
if root == nil {
return nil
}
cur := root
for cur != nil {
if cur.Left != nil {
// find current node's preorder node that links to current node's right subtree
prev := cur.Left
for prev.Right != nil {
prev = prev.Right
}
prev.Right = cur.Right
cur.Right = cur.Left
cur.Left = nil
}
cur = cur.Right
}
return utils.LevelOrderTravesal(root)
}