LeetCode Binary Search Tree Iterator

https://leetcode.com/problems/binary-search-tree-iterator/
Binary Search Tree 를 탐색해서 가장 작은 값부터 return 하는 프로그램이다.

이것은 맨 위의 node 가 중간 값을 가져가고, left 는 그보다 작고, right 는 그보다 큰 값들이 저장되어 있다. 빠지지 말아야 할 함정이 Level 0 의 node 가 20 이고 Left 가 15, Right 30 Level 1 의 Right 가 Level 0 의 node 보다 커서는 안된다는 것이다. 그 생각을 해보면 풀기 쉽다.

아이디어는 이렇다. inOrder 로 트리를 탐색하면서 stack 에 값을 쌓는 것이다. 단, 보통의 inOrder 처럼 Left, Root, Right 순이 아니라, Right, Root, Left 순. 트리를 읽게 되면 최우하단(제일 큰 값 부터) 읽어서 stack 맨 위에는 제일 작은 값이 있게 될 것이다.