-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmain.go
More file actions
44 lines (40 loc) · 825 Bytes
/
main.go
File metadata and controls
44 lines (40 loc) · 825 Bytes
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
package main
// Definition for a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// recursion
// time complexity: O(n)
// space complexity: O(n)
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
root.Left, root.Right = root.Right, root.Left
invertTree(root.Left)
invertTree(root.Right)
return root
}
// bfs
// time complexity: O(n)
// space complexity: O(n)
func invertTree2(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
queue := []*TreeNode{root}
for len(queue) > 0 {
element := queue[0]
queue = queue[1:]
element.Left, element.Right = element.Right, element.Left
if element.Left != nil {
queue = append(queue, element.Left)
}
if element.Right != nil {
queue = append(queue, element.Right)
}
}
return root
}