不同的二叉搜索樹

題目描述：給你一個整數(shù) n ，求恰由 n 個節(jié)點組成且節(jié)點值從 1 到 n 互不相同的 二叉搜索樹 有多少種？返回滿足題意的二叉搜索樹的種數(shù)。

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

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

來源：力扣（LeetCode） ??

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

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

解法一：遞歸法

• 首先，當n為0的時候，結果是一棵空樹，直接返回空的list。

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

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

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

• i右邊的所有的值遞歸調用方法作為i的右子樹；

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

• 最后，返回結果集的size值即為符合條件的二叉搜索樹的種數(shù)。

說明：該方法參照的 LeetCode-095-不同的二叉搜索樹 II，不過在提交的時候超時了。

解法一：規(guī)律

找規(guī)律可知，當整數(shù)為n時，二叉搜索數(shù)的結果是前面所有可能的結果之和。

【每日寄語】 年輕是本錢，但不努力就不值錢。