# 0096. 不同的二叉搜索樹 ## 題目地址（96. 不同的二叉搜索樹） <https://leetcode-cn.com/problems/unique-binary-search-trees/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個整數 n，求以 1 ... n 為節點組成的二叉搜索樹有多少種？ 示例: 輸入: 3 輸出: 5 解釋: 給定 n = 3, 一共有 5 種不同結構的二叉搜索樹: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 ``` ``` ## 前置知識 - 二叉搜索樹 - 分治 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 這是一個經典的使用分治思路的題目。 對于數字 n ，我們可以 1- n 這樣的離散整數分成左右兩部分。我們不妨設其分別為 A 和 B。那么問題轉化為 A 和 B 所能組成的 BST 的數量的笛卡爾積。而對于 A 和 B 以及原問題除了規模，沒有不同，這不就是分治思路么？至于此，我們只需要考慮邊界即可，邊界很簡單就是 n 小于等于 1 的時候，我們返回 1。 具體來說： - 生成一個\[1:n + 1\] 的數組 - 我們遍歷一次數組，對于每一個數組項，我們執行以下邏輯 - 對于每一項，我們都假設其是斷點。斷點左側的是 A，斷點右側的是 B。 - 那么 A 就是 i - 1 個數， 那么 B 就是 n - i 個數 - 我們遞歸，并將 A 和 B 的結果相乘即可。 > 其實我們發現，題目的答案只和 n 有關，和具體 n 個數的具體組成，只要是有序數組即可。 題目沒有明確 n 的取值范圍，我們試一下暴力遞歸。 代碼（Python3）： ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">numTrees</span><span class="hljs-params">(self, n: int)</span> -> int:</span> <span class="hljs-keyword">if</span> n <= <span class="hljs-params">1</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">1</span> res = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n + <span class="hljs-params">1</span>): res += self.numTrees(i - <span class="hljs-params">1</span>) * self.numTrees(n - i) <span class="hljs-keyword">return</span> res ``` ``` 上面的代碼會超時，并沒有棧溢出，因此我們考慮使用 hashmap 來優化，代碼見下方代碼區。 ## 關鍵點解析 - 分治法 - 笛卡爾積 - 記憶化遞歸 ## 代碼 - 語言支持：Python3 Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> visited = dict() <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">numTrees</span><span class="hljs-params">(self, n: int)</span> -> int:</span> <span class="hljs-keyword">if</span> n <span class="hljs-keyword">in</span> self.visited: <span class="hljs-keyword">return</span> self.visited.get(n) <span class="hljs-keyword">if</span> n <= <span class="hljs-params">1</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">1</span> res = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n + <span class="hljs-params">1</span>): res += self.numTrees(i - <span class="hljs-params">1</span>) * self.numTrees(n - i) self.visited[n] = res <span class="hljs-keyword">return</span> res ``` ``` **復雜度分析** - 時間復雜度：一層循環是 N，另外遞歸深度是 N，因此總的時間復雜度是 O(N2)O(N^2)O(N2) - 空間復雜度：遞歸的棧深度和visited 的大小都是 N，因此總的空間復雜度為 O(N)O(N)O(N) ## 相關題目 - [95.unique-binary-search-trees-ii](https://github.com/azl397985856/leetcode/blob/master/problems/95.unique-binary-search-trees-ii.md) 更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經30K star啦。 關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。