主題
題目連結：
題目意譯：
實作類別 BSTIterator，其代表著一個迭代器（Iterator）於一棵二元搜尋樹（Binary Search Tree，BST）的中序探訪（In-order Traversal）上移動：
BSTIterator(TreeNode root) 初始化一個類別 BSTIterator 之物件。該 BST 的根節點將作為建構子的參數之一傳入。指標（譯注：這邊是指涉用來迭代的指標）應初始化成指向一個比 BST 中所有元素都小之不存在的數字。
boolean hasNext() 回傳真（True）如果指標在探訪中存在一個數字位於其右；反之回傳假（False）。
int next() 將指標往右移動，並回傳指標現在指到的數字。
請注意到由於迭代用的指標一開始初始化是指到一個不存在的最小數字，因此第一次呼叫 next() 將會回傳 BST 中最小的元素。
你可以假設 next() 之呼叫永遠是合法的。也就是說在 next() 被呼叫的時候，在中序探訪中至少會有一個「下一個」數字。
限制：
樹中的節點數位於範圍 [1, 10 ^ 5] 中。
0 ≦ Node.val ≦ 10 ^ 6
hasNext 和 next 最多只會被呼叫 10 ^ 5 次。
進階：
你可以實作出 next() 和 hasNext() 並有著平均 O(1) 的時間複雜度並使用 O(h) 的空間複雜度嗎？其中 h 為樹的高度。
範例測資：
範例 1：
Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]
Explanation
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // 回傳 3
bSTIterator.next(); // 回傳 7
bSTIterator.hasNext(); // 回傳真
bSTIterator.next(); // 回傳 9
bSTIterator.hasNext(); // 回傳真
bSTIterator.next(); // 回傳 15
bSTIterator.hasNext(); // 回傳真
bSTIterator.next(); // 回傳 20
bSTIterator.hasNext(); // 回傳
解題思維：
首先很明顯的，跑一次中序探訪（如這題）然後再依序在 next() 中回傳這些數字是可行的方式。不過由於空間複雜度是 O(n)（其中 n 是這棵樹的節點數），所以不符合進階的要求。不過因為最多呼叫 n 次的 next()（hasNext() 就單純只是判斷我們有沒有到結尾而已），而預先做一次探訪 + 掃過整個中序探訪的結果也是 O(n)，因此平均確實是 O(1)。
現在我們來觀察以下這棵二元樹：
８
／ ＼
２ ９
／ ＼
１ ４
／ ＼
３ ５
而根據定義前序和中序探訪，它們的遞迴式依序是：
「根節點 → 左子樹 → 右子樹」和
「左子樹 → 根節點 → 右子樹 」
而前序探訪實際上就是一般深度優先搜尋（Depth First Search，DFS）走過整棵二元樹的節點順序。
然後上面那棵樹的中序探訪是 1 2 3 4 5 8 9；
而前序探訪為 8 2 1 3 4 5 9。然後我們把前序中的（整棵樹的）根節點以及每次往左的節點擷取出來，則是前三個數字：8 2 1。可以看到最後一個數字是最小的數字，也就是 BST 的中序之第一個數字。
以下把這個擷取後的前序探訪稱為 X，其中其內容將會在過程中一直變動。
目前 X 是 8 2 1
所以我們第一次呼叫 next()，將會回傳 1。然後把 1 從 X 中移除掉。
現在 X 是 8 2
第二次呼叫時，回傳的是 2。此時 2 本身的左子樹已經被探訪完了，而 2 本身有右子樹（也就是 3 、 4 、 5），所以我們先把 4 放進 X 中。而 4 有一個左子樹（即 3），所以我們同時也把 3 放進 X 中。
現在 X 是 8 2 4 3
第三次呼叫時，回傳的是 3。而因為 3 沒有左子樹和右子樹，所以直接把 3 移除即可。
現在 X 是 8 2 4
第四次呼叫時，回傳的是 4。而因為 4 還有一個右子樹，所以把 5 放進 X 中。
現在 X 是 8 2 4 5
第五次呼叫時，回傳的是 5。而因為 5 沒有左子樹和右子樹，所以直接把 5 移除即可。而因為 4 在先前回傳過了，而且我們也把其右子樹探訪過了。所以 4 可以從 X 中移除了（因為不會在中序探訪中再次出現，其子樹也不會）。同理，2 也是。所以 2 也被移除了。
現在 X 是 8
第六次呼叫時，回傳的是 8。而 8 還有右子樹（9），所以把 9 放進 X 中。
現在 X 是 8 9。
第七次呼叫時，回傳的是 9。而因為 9 沒有左子樹和右子樹，所以直接把 9 移除即可。而因為 8 在先前回傳過了，而且我們也把其右子樹探訪過了。所以 8 可以從 X 中移除了。
所以可以看到在中序探訪完成後，X 正好是空的。因此在 next() 在像上面的程序執行時，hasNext() 依舊維持原本、單純的判斷 X 是不是空的即可判斷中序探訪有沒有完成。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
