題目描述
給定一個整數 n，生成所有由 1 ... n 為節點所組成的 二叉搜索樹 。
示例
輸入：3
輸出：
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解釋：
以上的輸出對應以下 5 種不同結構的二叉搜索樹：
官方的圖
聲明
本文答案參考自 LeetCode 官方題解。[敲打]
講個騷話順便科普一下“二叉搜索樹”
好家伙，先有Ⅱ呢~[奸笑][看]
二叉搜索樹關鍵的性質是根節點的值 大于 左子樹所有節點的值，小于 右子樹所有節點的值，且左子樹和右子樹也同樣為二叉搜索樹。
解法：遞歸
樹這種東西，經常需要考慮遞歸。
因為 二叉搜索樹某一結點的左子樹和右子樹也同樣為二叉搜索樹。
所以，對于這道題：
- 要生成 [1 , n] 的二叉搜索樹，我們可以把 [1 , n] 拆分為 [ 1 , i ] 和 [ i , n]
- 分別對 [ 1 , i ] 和 [ i , n] 求其生成的二叉搜索樹
- 然后再把第2步中的兩棵子二叉搜索樹 拼接在一起
就這樣一層一層地拆分下去，然后再層層返回，我們就可以得到二叉搜索樹了。
遞歸就是這樣，我們的思路是清晰的，代碼也是簡潔的，但是在分析代碼運行的過程就有點懵。所以我們就盡量不要想太多，思路對就行了[呲牙]
這里的 i 可以取 1 ~ n 之間，因為題目說是要 生成 所有的 二叉搜索樹 。
