{"id":2015,"date":"2018-03-07T09:20:29","date_gmt":"2018-03-07T17:20:29","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2015"},"modified":"2018-09-03T10:50:25","modified_gmt":"2018-09-03T17:50:25","slug":"leetcode-95-unique-binary-search-trees-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/uncategorized\/leetcode-95-unique-binary-search-trees-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 95. Unique Binary Search Trees II"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

https:\/\/leetcode.com\/problems\/unique-binary-search-trees-ii\/description\/<\/a><\/p>\n

Given an integer\u00a0n<\/i>, generate all structurally unique\u00a0BST’s<\/b>\u00a0(binary search trees) that store values 1…n<\/i>.<\/p>\n

For example,
\nGiven\u00a0n<\/i>\u00a0= 3, your program should return all 5 unique BST’s shown below.<\/p>\n

   1         3     3      2      1\r\n    \\       \/     \/      \/ \\      \\\r\n     3     2     1      1   3      2\r\n    \/     \/       \\                 \\\r\n   2     1         2                 3\r\n<\/pre>\n
\u00a0<\/ins><\/p>\n
Idea: Recursion<\/strong><\/h1>\n
for i in 1..n: pick i as root,
\nleft subtrees can be generated in the same way for n_l = 1 … i – 1,
\nright subtrees can be generated in the same way for n_r = i + 1, …, n
\ndef gen(s, e):
\nreturn [tree(i, l, r) for l in gen(s, i – 1) for r in gen(i + 1, e) for i in range(s, e+1)<\/p>\n
# of trees:<\/p>\n
n = 0: 1
\nn = 1: 1
\nn = 2: 2
\nn = 3: 5
\nn = 4: 14
\nn = 5: 42
\nn = 6: 132
\n…
\nTrees(n) = Trees(0)*Trees(n-1) + Trees(1)*Trees(n-2) + … + Tress(n-1)*Trees(0)<\/p>\n
Time complexity: O(3^n)<\/p>\n
Space complexity: O(3^n)<\/p>\n
\n
C++<\/h2>\n
\n\n
\/\/ Author: Huahua\r\n\/\/ Running time: 16 ms\r\nclass Solution {\r\npublic:\r\n  vector<TreeNode*> generateTrees(int n) {\r\n    if (n == 0) return {};\r\n    const auto& ans = generateTrees(1, n);\r\n    cout << ans.size() << endl;\r\n    return ans;\r\n  }\r\nprivate:\r\n  vector<TreeNode*> generateTrees(int l, int r) {\r\n    if (l > r) return { nullptr };\r\n    vector<TreeNode*> ans;\r\n    for (int i = l; i <= r; ++i)\r\n      for (TreeNode* left : generateTrees(l, i - 1))\r\n        for (TreeNode* right : generateTrees(i + 1, r)) {\r\n          ans.push_back(new TreeNode(i));\r\n          ans.back()->left = left;\r\n          ans.back()->right = right;\r\n        }\r\n    return ans;\r\n  }\r\n};<\/pre>\n\n<\/div>
Java<\/h2>\n
\n\n
\/\/ Author: Huahua 4 ms\r\nclass Solution {\r\n  public List<TreeNode> generateTrees(int n) {\r\n    if (n == 0) return new ArrayList<TreeNode>();\r\n    return generateTrees(1, n);\r\n  }\r\n  \r\n  private List<TreeNode> generateTrees(int l, int r) {\r\n    List<TreeNode> ans = new ArrayList<>();\r\n    if (l > r) {      \r\n      ans.add(null);\r\n      return ans;\r\n    }\r\n    for (int i = l; i <= r; ++i)\r\n      for (TreeNode left : generateTrees(l, i - 1))\r\n        for (TreeNode right: generateTrees(i + 1, r)) {\r\n          TreeNode root = new TreeNode(i);\r\n          root.left = left;\r\n          root.right = right;\r\n          ans.add(root);\r\n        }          \r\n    return ans;\r\n  }\r\n}<\/pre>\n\n<\/div>
Python 3<\/h2>\n
\n\n
\"\"\"\r\nAuthor: Huahua\r\nRunning time: 84 ms\r\n\"\"\"\r\nclass Solution:\r\n  def generateTrees(self, n):\r\n    def newTree(x, l, r): \r\n      t = TreeNode(x)\r\n      t.left = l\r\n      t.right = r\r\n      return t\r\n    \r\n    def gen(s, e):      \r\n      return [newTree(i, l, r) for i in range(s, e + 1) for l in gen(s, i - 1) for r in gen(i + 1, e)] or [None]\r\n        \r\n    return gen(1, n) if n > 0 else []<\/pre>\n<\/div><\/div>\n
Solution 2: DP<\/h1>\n
\n
Java<\/h2>\n
\n\n
\/\/ Author: Huahua, 3 ms\r\nclass Solution {\r\n  public List<TreeNode> generateTrees(int n) {\r\n    if (n == 0) return new ArrayList<TreeNode>();\r\n    List<TreeNode>[] dp = new List[n + 1];\r\n    dp[0] = new ArrayList<TreeNode>();\r\n    dp[0].add(null);\r\n    for (int i = 1; i <= n; ++i) {\r\n      dp[i] = new ArrayList<TreeNode>();\r\n      for (int j = 0; j < i; ++j)\r\n        for (TreeNode left : dp[j])\r\n          for (TreeNode right: dp[i - j - 1]) {\r\n            TreeNode root = new TreeNode(j + 1);\r\n            root.left = left;\r\n            root.right = clone(right, j + 1);\r\n            dp[i].add(root);\r\n        }          \r\n      }\r\n    return dp[n];\r\n  }\r\n  \r\n  private TreeNode clone(TreeNode root, int delta) {\r\n    if (root == null) return root;\r\n    TreeNode node = new TreeNode(root.val + delta);\r\n    node.left = clone(root.left, delta);\r\n    node.right = clone(root.right, delta);\r\n    return node;\r\n  }\r\n}<\/pre>\n<\/div><\/div>\n
Related Problems<\/strong><\/h1>\n