forked from spring1843/go-dsa
-
Notifications
You must be signed in to change notification settings - Fork 0
/
is_tree_symmetrical.go
50 lines (41 loc) · 1.11 KB
/
is_tree_symmetrical.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
package queue
import (
"github.com/spring1843/go-dsa/tree"
)
type queue struct {
data []*tree.BinaryTreeNode
}
// IsTreeSymmetrical solves the problem in O(n) time and O(n) space.
func IsTreeSymmetrical(root *tree.BinaryTreeNode) (bool, error) {
if root == nil {
return false, nil
}
q1 := new(queue)
q2 := new(queue)
q1.enqueue(root)
q2.enqueue(root)
for q1.len() != 0 {
tmp1 := q1.dequeue()
tmp2 := q2.dequeue()
unsymmetrical := tmp1.Val != tmp2.Val || tmp1.Left != nil && tmp2.Right == nil || tmp1.Left == nil && tmp2.Right != nil || tmp1.Right != nil && tmp2.Left == nil || tmp1.Right == nil && tmp2.Left != nil
if unsymmetrical {
return false, nil
}
if tmp1.Left != nil {
q1.enqueue(tmp1.Left)
q2.enqueue(tmp2.Right)
}
if tmp1.Right != nil {
q1.enqueue(tmp1.Right)
q2.enqueue(tmp2.Left)
}
}
return true, nil
}
func (q *queue) len() int { return len(q.data) }
func (q *queue) enqueue(val *tree.BinaryTreeNode) { q.data = append(q.data, val) }
func (q *queue) dequeue() *tree.BinaryTreeNode {
tmp := q.data[0]
q.data = q.data[1:len(q.data)]
return tmp
}