主題
題目連結：
題目意譯：
給定一個二元搜尋樹（Binary Search Tree，BST）的根節點 root 以及一整數 k，回傳樹中節點值第 k 小（索引值從 1 開始數）的數值。
限制：
樹中的節點數為 n。
1 ≦ k ≦ n ≦ 10 ^ 4
0 ≦ Node.val ≦ 10 ^ 4
進階：如果該 BST 經常被修改（即我們可以執行插入或是刪除之指令）而你時常需要知道第 k 小的數字，你會怎麼最佳化這個流程？
範例測資：
範例 1：
輸入： root = [3,1,4,null,2], k = 1
輸出： 1
範例 2：
輸入： root = [5,3,6,2,4,null,null,1], k = 3
輸出： 3
解題思維：
以前有提及過 BST 的中序探訪（Inorder Traversal）是一個排序的數列（如這題），因此可以直接對著 BST 中序探訪一次（用遞迴或是迭代都可以），數到第 k 個元素即是第 k 小的數字。
而時間複雜度不論是遞迴還是迭代都是 O(h + k)，其中 h 為樹的高度。因此對於平衡的 BST，時間是 O(log n + k)；對於不平衡的（尤其是對於所有節點只有左子樹的）則是會退化成 O(n + k)。
那進階提及的問題呢？可以看到在不做任何其他改動的情況下，當我們遇到一次插入（或是刪除）接著一次詢問第 k 小元素時，可以看到其總體時間複雜度為 O(h) + O(h + k) = O(2h + k)。
對於數量級而言，2h + k 跟 h + k 是一樣的；但是對於實際上的程式執行來說，我們會掃過兩次樹（一次插入、一次探訪），運行時間還是會有一些差距。
而我們已經知道會經常地使用這棵樹，因此可以犧牲一點空間直接使用連結串列（Linked List）把整個中序探訪的序列存下來，以及除了串列以外還需要建立串列元素與樹中的節點之對應（看到樹中的節點，就可以知道該節點值位於串列的何處；反之亦然）。這樣子便可以只需要掃過一次來執行插入和刪除（此為 O(h)），然後同時對串列進行相對應的更新（此為 O(1)），最後在串列找第 k 個元素即可得到所求（此為 O(k)）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
