LeetCode: Unique Binary Search Trees II
Given 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.
confused what
再帰的にBSTを低から上へ順次確立する.
For example, Given n = 3, your program should return all 5 unique BST's shown below.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
confused what
"{1,#,2,3}" means? > read more on how binary tree is serialized on OJ. 再帰的にBSTを低から上へ順次確立する.
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void build(vector<TreeNode*> &result, int nStart, int nEnd)
{
if (nStart > nEnd)
result.push_back(NULL);
else
{
for (int i = nStart; i <= nEnd; ++i)
{
vector<TreeNode*> left;
build(left, nStart, i-1);
vector<TreeNode*> right;
build(right, i+1, nEnd);
for (int j = 0; j < left.size(); ++j)
{
for (int k = 0; k < right.size(); ++k)
{
TreeNode* root = new TreeNode(i);
root->left = left[j];
root->right = right[k];
result.push_back(root);
}
}
}
}
}
vector<TreeNode *> generateTrees(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<TreeNode*> result;
build(result, 1, n);
return result;
}
};