95.Unique Binary Search Trees II¶
Tags: Medium
Dynamic Programming
Tree
Links: https://leetcode.com/problems/unique-binary-search-trees-ii/
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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
if (n == 0) return {};
return solve(1, n);
}
vector<TreeNode*> solve(int start, int end)
{
if (start > end) return {nullptr};
vector<TreeNode*> res;
for (int i = start; i <= end; ++i) {
auto left = solve(start, i - 1), right = solve(i + 1, end);
for (auto a : left) {
for (auto b : right) {
TreeNode *root = new TreeNode(i);
root -> left = a;
root -> right = b;
res.push_back(root);
}
}
}
return res;
}
};
采用分治+递归的做法。
划分左右两个子数组,递归构造。刚开始时,将区间 [1, n] 当作一个整体,然后需要将其中的每个数字都当作根结点,其划分开了左右两个子区间,然后分别调用递归函数,会得到两个结点数组,接下来要做的就是从这两个数组中每次各取一个结点,当作当前根结点的左右子结点,然后将根结点加入结果 res 数组中即可