Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.
Example 1:
Input: n = 3 Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
Example 2:
Input: n = 1 Output: [[1]]
Constraints:
1 <= n <= 8
Companies: Adobe, Bloomberg, Uber
Related Topics:
Dynamic Programming, Backtracking, Tree, Binary Search Tree, Binary Tree
Similar Questions:
Pick a number i for root node.
Numbers [1, i - 1] should be put on the left sub-tree, while [i + 1, N] on the right.
Both of them are sub-problems. We can simply repeat this process.
// OJ: https://leetcode.com/problems/unique-binary-search-trees-ii/
// Author: github.com/lzl124631x
// Time: O(N*C(N)) where C(N) is Catalan Number which equals
// the count of unique BST. For each tree we visit each node once.
// Space: O(C(N)) because the intermediate `lefts` and `rights` vectors.
// The actual nodes and the returned vector are not counted as consumptions.
class Solution {
vector<TreeNode*> dfs(int first, int last) {
if (first > last) return {nullptr};
vector<TreeNode*> ans;
for (int i = first; i <= last; ++i) {
for (auto left : dfs(first, i - 1)) {
for (auto right : dfs(i + 1, last)) {
ans.push_back(new TreeNode(i, left, right));
}
}
}
return ans;
}
public:
vector<TreeNode*> generateTrees(int n) {
return dfs(1, n);
}
};