Problem#
給你一個二元搜尋樹(Binary Search Tree, BST)，問你樹上所有點相差最小的是多少？
測資限制#
- $2 \le n \le 10^4$
- $0 \le val \le 10^5$
想法#
要找到所有點數值相差最小，首先就是要把樹遍歷過，把所有點蒐集在 array 中 $O(n)$
接著找數值相差最小，當然可以直接暴力找 $O(n^2)$，但是因為要找的是相差最小，而如果把陣列由小排到大，則對於 $i$ ，和它相差最小只會是 $i-1$ 或 $i+1$ ($0 \le i \le n-1$)
所以就可以直接掃一遍，相鄰的數字相減找最小即可 $O(n)$。
但別忘記了還要把陣列從小排到大，可以直接用 std::sort $O(n\log{n})$，或是在遍歷整顆樹的時候，用中序(In-Order)的方式遍歷，蒐集好的 array 會是已經排好序的，因為 bst 的性質： $O(n)$。
- 空間複雜度: $\mathcal{O}(n)$
AC Code#
賞析#
官方題解：也可以不用蒐集成一個 array，而是記住上個訪問的 node，如此在中序遍歷仍可以算用前後相減找最小。
心得#
一開始以為這種有 struct TreeNode 題目都不讓你裝成 array，結果官方題解就寫了這種方法XDD