Problem
https://leetcode.com/problems/unique-binary-search-trees-ii/description/
Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.
For example,
Given n = 3, your program should return all 5 unique BST’s shown below.
|
1 2 3 4 5 |
1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 |
Idea: Recursion
for i in 1..n: pick i as root,
left subtrees can be generated in the same way for n_l = 1 … i – 1,
right subtrees can be generated in the same way for n_r = i + 1, …, n
def gen(s, e):
return [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)
# of trees:
n = 0: 1
n = 1: 1
n = 2: 2
n = 3: 5
n = 4: 14
n = 5: 42
n = 6: 132
…
Trees(n) = Trees(0)*Trees(n-1) + Trees(1)*Trees(n-2) + … + Tress(n-1)*Trees(0)
Time complexity: O(3^n)
Space complexity: O(3^n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua // Running time: 16 ms class Solution { public: vector<TreeNode*> generateTrees(int n) { if (n == 0) return {}; const auto& ans = generateTrees(1, n); cout << ans.size() << endl; return ans; } private: vector<TreeNode*> generateTrees(int l, int r) { if (l > r) return { nullptr }; vector<TreeNode*> ans; for (int i = l; i <= r; ++i) for (TreeNode* left : generateTrees(l, i - 1)) for (TreeNode* right : generateTrees(i + 1, r)) { ans.push_back(new TreeNode(i)); ans.back()->left = left; ans.back()->right = right; } return ans; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua 4 ms class Solution { public List<TreeNode> generateTrees(int n) { if (n == 0) return new ArrayList<TreeNode>(); return generateTrees(1, n); } private List<TreeNode> generateTrees(int l, int r) { List<TreeNode> ans = new ArrayList<>(); if (l > r) { ans.add(null); return ans; } for (int i = l; i <= r; ++i) for (TreeNode left : generateTrees(l, i - 1)) for (TreeNode right: generateTrees(i + 1, r)) { TreeNode root = new TreeNode(i); root.left = left; root.right = right; ans.add(root); } return ans; } } |
Python 3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
""" Author: Huahua Running time: 84 ms """ class Solution: def generateTrees(self, n): def newTree(x, l, r): t = TreeNode(x) t.left = l t.right = r return t def gen(s, e): 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] return gen(1, n) if n > 0 else [] |
Solution 2: DP
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Author: Huahua, 3 ms class Solution { public List<TreeNode> generateTrees(int n) { if (n == 0) return new ArrayList<TreeNode>(); List<TreeNode>[] dp = new List[n + 1]; dp[0] = new ArrayList<TreeNode>(); dp[0].add(null); for (int i = 1; i <= n; ++i) { dp[i] = new ArrayList<TreeNode>(); for (int j = 0; j < i; ++j) for (TreeNode left : dp[j]) for (TreeNode right: dp[i - j - 1]) { TreeNode root = new TreeNode(j + 1); root.left = left; root.right = clone(right, j + 1); dp[i].add(root); } } return dp[n]; } private TreeNode clone(TreeNode root, int delta) { if (root == null) return root; TreeNode node = new TreeNode(root.val + delta); node.left = clone(root.left, delta); node.right = clone(root.right, delta); return node; } } |
Related Problems
