this repo has no description
tulkdan.dev
1package main
2
3type TreeNode struct {
4 Val int
5 Left, Right *TreeNode
6}
7
8type QueueNode struct {
9 node *TreeNode
10 next *QueueNode
11}
12
13type Queue struct {
14 first *QueueNode
15 Size int
16}
17
18func (q *Queue) Insert(node *TreeNode) {
19 toInsert := &QueueNode{node: node}
20 q.Size++
21 if q.first == nil {
22 q.first = toInsert
23 return
24 }
25
26 toInsert.next = q.first
27 q.first = toInsert
28}
29
30func (q *Queue) Pop() *TreeNode {
31 if q.first == nil {
32 return nil
33 }
34
35 if q.Size > 0 {
36 q.Size--
37 }
38
39 toReturn := q.first.node
40 q.first = q.first.next
41
42 return toReturn
43}
44
45func (q *Queue) Empty() bool {
46 return q.first != nil
47}
48
49func smallInQueue(root *TreeNode, q *Queue, k int) *TreeNode {
50 if root.Left != nil {
51 left := smallInQueue(root.Left, q, k)
52
53 if left != nil {
54 return left
55 }
56 }
57
58 q.Insert(root)
59
60 if q.Size == k {
61 return q.Pop()
62 }
63
64 if root.Right != nil {
65 right := smallInQueue(root.Right, q, k)
66 if right != nil {
67 return right
68 }
69 }
70
71 return nil
72}
73
74func kthSmallest(root *TreeNode, k int) int {
75 result := smallInQueue(root, &Queue{Size: 0}, k)
76 if result != nil {
77 return result.Val
78 } else {
79 return -1
80 }
81}
82