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

# Unique Binary Search Trees II ### Source - leetcode: [Unique Binary Search Trees II | LeetCode OJ](https://leetcode.com/problems/unique-binary-search-trees-ii/) - lintcode: [(164) Unique Binary Search Trees II](http://www.lintcode.com/en/problem/unique-binary-search-trees-ii/) ~~~ Given n, generate all structurally unique BST's (binary search trees) that store values 1...n. Example Given n = 3, your program should return all 5 unique BST's shown below. 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 ~~~ ### 題解題 [Unique Binary Search Trees](http://algorithm.yuanbin.me/zh-cn/math_and_bit_manipulation/unique_binary_search_trees.html) 的升級版，這道題要求的不是二叉搜索樹的數目，而是要構建這樣的樹。分析方法仍然是可以借鑒的，核心思想為利用『二叉搜索樹』的定義，如果以 i 為根節點，那么其左子樹由[1, i - 1]構成，右子樹由[i + 1, n] 構成。要構建包含1到n的二叉搜索樹，只需遍歷1到n中的數作為根節點，以`i`為界將數列分為左右兩部分，小于`i`的數作為左子樹，大于`i`的數作為右子樹，使用兩重循環將左右子樹所有可能的組合鏈接到以`i`為根節點的節點上。容易看出，以上求解的思路非常適合用遞歸來處理，接下來便是設計遞歸的終止步、輸入參數和返回結果了。由以上分析可以看出遞歸嚴重依賴數的區間和`i`，那要不要將`i`也作為輸入參數的一部分呢？首先可以肯定的是必須使用『數的區間』這兩個輸入參數，又因為`i`是隨著『數的區間』這兩個參數的，故不應該將其加入到輸入參數中。分析方便，不妨設『數的區間』兩個輸入參數分別為`start`和`end`. 接下來談談終止步的確定，由于根據`i`拆分左右子樹的過程中，遞歸調用的方法中入口參數會縮小，且存在`start <= i <= end`, 故終止步為`start > end`. 那要不要對`start == end`返回呢？保險起見可以先寫上，后面根據情況再做刪改。總結以上思路，簡單的偽代碼如下： ~~~ helper(start, end) { result; if (start > end) { result.push_back(NULL); return; } else if (start == end) { result.push_back(TreeNode(i)); return; } // dfs for (int i = start; i <= end; ++i) { leftTree = helper(start, i - 1); rightTree = helper(i + 1, end); // link left and right sub tree to the root i for (j in leftTree ){ for (k in rightTree) { root = TreeNode(i); root->left = leftTree[j]; root->right = rightTree[k]; result.push_back(root); } } } return result; } ~~~ 大致的框架如上所示，我們來個簡單的數據驗證下，以[1, 2, 3]為例，調用堆棧圖如下所示： 1. helper(1,3) - [leftTree]: helper(1, 0) ==> return NULL - ---loop i = 2--- - [rightTree]: helper(2, 3) 1. [leftTree]: helper(2,1) ==> return NULL 1. [rightTree]: helper(3,3) ==> return node(3) 1. [for loop]: ==> return (2->3) - ---loop i = 3--- 1. [leftTree]: helper(2,2) ==> return node(2) 1. [rightTree]: helper(4,3) ==> return NULL 1. [for loop]: ==> return (3->2) 1. ... 簡單驗證后可以發現這種方法的**核心為遞歸地構造左右子樹并將其鏈接到相應的根節點中。**對于`start`和`end`相等的情況的，其實不必單獨考慮，因為`start == end`時其左右子樹均返回空，故在`for`循環中返回根節點。當然單獨考慮可減少遞歸棧的層數，但實際測下來后發現運行時間反而變長了不少 :( ### Python ~~~ """ Definition of TreeNode: class TreeNode: def __init__(self, val): this.val = val this.left, this.right = None, None """ class Solution: # @paramn n: An integer # @return: A list of root def generateTrees(self, n): return self.helper(1, n) def helper(self, start, end): result = [] if start > end: result.append(None) return result for i in xrange(start, end + 1): # generate left and right sub tree leftTree = self.helper(start, i - 1) rightTree = self.helper(i + 1, end) # link left and right sub tree to root(i) for j in xrange(len(leftTree)): for k in xrange(len(rightTree)): root = TreeNode(i) root.left = leftTree[j] root.right = rightTree[k] result.append(root) return result ~~~ ### C++ ~~~ /** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @paramn n: An integer * @return: A list of root */ vector<TreeNode *> generateTrees(int n) { return helper(1, n); } private: vector<TreeNode *> helper(int start, int end) { vector<TreeNode *> result; if (start > end) { result.push_back(NULL); return result; } for (int i = start; i <= end; ++i) { // generate left and right sub tree vector<TreeNode *> leftTree = helper(start, i - 1); vector<TreeNode *> rightTree = helper(i + 1, end); // link left and right sub tree to root(i) for (int j = 0; j < leftTree.size(); ++j) { for (int k = 0; k < rightTree.size(); ++k) { TreeNode *root = new TreeNode(i); root->left = leftTree[j]; root->right = rightTree[k]; result.push_back(root); } } } return result; } }; ~~~ ### Java ~~~ /** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @paramn n: An integer * @return: A list of root */ public List<TreeNode> generateTrees(int n) { return helper(1, n); } private List<TreeNode> helper(int start, int end) { List<TreeNode> result = new ArrayList<TreeNode>(); if (start > end) { result.add(null); return result; } for (int i = start; i <= end; i++) { // generate left and right sub tree List<TreeNode> leftTree = helper(start, i - 1); List<TreeNode> rightTree = helper(i + 1, end); // link left and right sub tree to root(i) for (TreeNode lnode: leftTree) { for (TreeNode rnode: rightTree) { TreeNode root = new TreeNode(i); root.left = lnode; root.right = rnode; result.add(root); } } } return result; } } ~~~ ### 源碼分析 1. 異常處理，返回None/NULL/null. 1. 遍歷start->end, 遞歸得到左子樹和右子樹。 1. 兩重`for`循環將左右子樹的所有可能組合添加至最終返回結果。注意 [DFS](# "Depth-First Search, 深度優先搜索") 輔助方法`helper`中左右子樹及返回根節點的順序。 ### 復雜度分析遞歸調用，一個合理的數組區間將生成新的左右子樹，時間復雜度為指數級別，使用的臨時空間最后都被加入到最終結果，空間復雜度(堆)近似為 O(1)O(1)O(1), 棧上的空間較大。 ### Reference - [Code Ganker: Unique Binary Search Trees II -- LeetCode](http://codeganker.blogspot.com/2014/04/unique-binary-search-trees-ii-leetcode.html) - [水中的魚: [LeetCode] Unique Binary Search Trees II, Solution](http://fisherlei.blogspot.com/2013/03/leetcode-unique-binary-search-trees-ii.html) - [Accepted Iterative Java solution. - Leetcode Discuss](https://leetcode.com/discuss/22821/accepted-iterative-java-solution) - [Unique Binary Search Trees II 參考程序 Java/C++/Python](http://www.jiuzhang.com/solutions/unique-binary-search-trees-ii/)