不同的二叉搜索樹 II

題目描述：給你一個整數(shù) n ，請你生成并返回所有由 n 個節(jié)點組成且節(jié)點值從 1 到 n 互不相同的不同 二叉搜索樹 。可以按 任意順序 返回答案。

二叉搜索樹（Binary Search Tree）：又稱二叉排序樹，它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹： 若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值； 若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值； 它的左、右子樹也分別為二叉排序樹。

示例說明請見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解法一：遞歸法

• 首先，當(dāng)n為0的時候，結(jié)果是一棵空樹，直接返回空的list。

• 當(dāng)n大于0的時候，使用遞歸的方法來分別獲取左右子樹，遞歸過程如下：

• 所有節(jié)點都可以作為根節(jié)點，也就是遍歷從1到n的所有值作為根節(jié)點，當(dāng)前根節(jié)點為i；

• 然后i左邊的所有的值遞歸調(diào)用方法作為i的左子樹；

• i右邊的所有的值遞歸調(diào)用方法作為i的右子樹；

• 最后把根節(jié)點i和相應(yīng)的左右子樹拼成一棵樹，放到結(jié)果集中。

• 最后，返回結(jié)果集即為所有可能的二叉搜索樹。

【每日寄語】 莫等閑，白了少年頭，空悲切！