Unique Binary Search Trees · 數據結構與算法/leetcode/lintcode題解

# Unique Binary Search Trees ### Source - leetcode: [Unique Binary Search Trees | LeetCode OJ](https://leetcode.com/problems/unique-binary-search-trees/) - lintcode: [(163) Unique Binary Search Trees](http://www.lintcode.com/en/problem/unique-binary-search-trees/) ~~~ Given n, how many structurally unique BSTs (binary search trees) that store values 1...n? Example Given n = 3, there are a total of 5 unique BST's. 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 ~~~ ### 題解1 - 兩重循環挺有意思的一道題，與數據結構和動態規劃都有點關系。這兩天在騎車路上和睡前都一直在想，始終未能找到非常明朗的突破口，直到看到這么一句話——『以i為根節點的樹，其左子樹由[0, i-1]構成，其右子樹由[i+1, n]構成。』這不就是 BST 的定義嘛！靈活運用下就能找到遞推關系了。容易想到這道題的動態規劃狀態為 count[n], count[n] 表示到正整數 i 為止的二叉搜索樹個數。容易得到 count[1] = 1, 根節點為1，count[2] = 2, 根節點可為1或者2。那么 count[3] 的根節點自然可為1，2，3. 如果以1為根節點，那么根據 BST 的定義，2和3只可能位于根節點1的右邊；如果以2為根節點，則1位于左子樹，3位于右子樹；如果以3為根節點，則1和2必位于3的左子樹。抽象一下，如果以 i 作為根節點，由基本的排列組合知識可知，其唯一 BST 個數為左子樹的 BST 個數乘上右子樹的 BST 個數。故對于 i 來說，其左子樹由[0, i - 1]構成，唯一的 BST 個數為 count[i - 1], 右子樹由[i + 1, n] 構成，其唯一的 BST 個數沒有左子樹直觀，但是也有跡可循。對于兩組有序數列「1, 2, 3] 和 [4, 5, 6]來說，**這兩個有序數列分別組成的 BST 個數必然是一樣的，因為 BST 的個數只與有序序列的大小有關，而與具體值沒有關系。**所以右子樹的 BST 個數為 count[n - i]，于是乎就得到了如下遞推關系：count[i]=∑j=0i?1(count[j]?count[i?j?1])count[i] = \sum _{j = 0} ^{i - 1} (count[j] \cdot count[i - j - 1])count[i]=∑j=0i?1(count[j]?count[i?j?1]) 網上有很多用 count[3] 的例子來得到遞推關系，恕本人愚笨，在沒有從 BST 的定義和有序序列個數與 BST 關系分析的基礎上，我是不敢輕易說就能得到如上狀態轉移關系的。 ### Python ~~~ class Solution: # @paramn n: An integer # @return: An integer def numTrees(self, n): if n < 0: return -1 count = [0] * (n + 1) count[0] = 1 for i in xrange(1, n + 1): for j in xrange(i): count[i] += count[j] * count[i - j - 1] return count[n] ~~~ ### C++ ~~~ class Solution { public: /** * @paramn n: An integer * @return: An integer */ int numTrees(int n) { if (n < 0) { return -1; } vector<int> count(n + 1); count[0] = 1; for (int i = 1; i != n + 1; ++i) { for (int j = 0; j != i; ++j) { count[i] += count[j] * count[i - j - 1]; } } return count[n]; } }; ~~~ ### Java ~~~ public class Solution { /** * @paramn n: An integer * @return: An integer */ public int numTrees(int n) { if (n < 0) { return -1; } int[] count = new int[n + 1]; count[0] = 1; for (int i = 1; i < n + 1; ++i) { for (int j = 0; j < i; ++j) { count[i] += count[j] * count[i - j - 1]; } } return count[n]; } } ~~~ ### 源碼分析 1. 對 n 小于0特殊處理。 1. 初始化大小為 n + 1 的數組，初始值為0，但對 count[0] 賦值為1. 1. 兩重 for 循環遞推求得 count[i] 的值。 1. 返回 count[n] 的值。由于需要處理空節點的子樹，故初始化 count[0] 為1便于乘法處理。其他值必須初始化為0，因為涉及到累加操作。 ### 復雜度分析一維數組大小為 n + 1, 空間復雜度為 O(n+1)O(n + 1)O(n+1). 兩重 for 循環等差數列求和累計約 n2/2n^2 / 2n2/2, 故時間復雜度為 O(n2)O(n^2)O(n2). 此題為 Catalan number 的一種，除了平方時間復雜度的解法外還存在 O(n)O(n)O(n) 的解法，欲練此功，先戳 [Wikipedia](http://en.wikipedia.org/wiki/Catalan_number) 的鏈接。 ### Reference - fisherlei > . [水中的魚: [LeetCode] Unique Binary Search Trees, Solution](http://fisherlei.blogspot.com/2013/03/leetcode-unique-binary-search-trees.html)[ ?](# "Jump back to footnote [fisherlei] in the text.") - [Unique Binary Search Trees | 九章算法](http://www.jiuzhang.com/solutions/unique-binary-search-trees/) - [Catalan number - Wikipedia, the free encyclopedia](http://en.wikipedia.org/wiki/Catalan_number)