Skip to content

BST(Binary Search Tree)

문제

https://leetcode.com/problems/binary-search-tree-iterator/

만약, binary search tree를 재귀적으로 순회하지 않고, generator를 만들고자 한다면,

방법은 다음과 같다.

  1. root노드를 기준으로 가장 왼쪽에 있는 값(leftmost라고 하자)이 가장 작은 값이 됨
  2. 그 다음 값을 찾는 방법은 다음과 같다.
  3. 만약 leftmost의 오른쪽 자식노드가 있다면, 오른쪽 자식노드의 leftmost를 한 번 더 찾아 들어간 것이 다음 노드가 된다.
  4. 만약 leftmost의 오른쪽 자식노드가 없다면, 부모 노드의 오른쪽 자식노드의 leftmost를 한 번 더 찾아 들어간 것이 다음 노드가 된다.
  5. 부모의 노드를 알기 위해서는 stack을 사용해서 기록하는 것이 좋다.

내 풀이(golang)

 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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type BSTIterator struct {
    Stack []*TreeNode
}


func Constructor(root *TreeNode) BSTIterator {
    // create Iterator
    // find leftmost
    bst := BSTIterator{}
    for root != nil {
        bst.Stack = append(bst.Stack, root)
        root = root.Left
    }
    return bst
}


func (this *BSTIterator) Next() int {
    // pop
    rslt := this.Stack[len(this.Stack)-1]
    this.Stack = this.Stack[:len(this.Stack)-1]

    if rslt.Right != nil {
        leftmost := rslt.Right
        for leftmost != nil {
            this.Stack = append(this.Stack, leftmost)
            leftmost = leftmost.Left
        }
    }
    return rslt.Val
}


func (this *BSTIterator) HasNext() bool {
    if len(this.Stack) > 0 {
        return true
    } else {
        return false
    }
}


/**
 * Your BSTIterator object will be instantiated and called as such:
 * obj := Constructor(root);
 * param_1 := obj.Next();
 * param_2 := obj.HasNext();
 */