Open GH1995 opened 5 years ago
Difficulty: Medium
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.
Example:
Input: 3 Output: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ] Explanation: The above output corresponds to the 5 unique BST's shown below: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
Language: C++
class Solution { public: vector<TreeNode *> generateTrees(int n) { if (n == 0) return {}; return dfs(1, n); } vector<TreeNode *> dfs(int start, int end) { if (start > end) return {nullptr}; vector<TreeNode *> result; for (int i = start; i <= end; ++i) { auto left = dfs(start, i - 1); auto right = dfs(i + 1, end); for (auto a : left) for (auto b:right) { auto node = new TreeNode(i); node->left = a; node->right = b; result.push_back(node); } } return result; } };
95. Unique Binary Search Trees II
Difficulty: Medium
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.
Example:
Solution
Language: C++