描述
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.
分析
上一题是leetcode-96-Unique-Binary-Search-Trees,只需要得到个数,而这道题是把所有的二叉搜索树都输出。
解决方案1(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 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
|
class Solution { public: vector<TreeNode*> generateTrees(int n) { vector<TreeNode *> result; if(n == 0) { return result; } return generate(1, n); } private: vector<TreeNode*> generate(int start, int end) { vector<TreeNode *> result; if(start > end) { result.push_back(NULL); return result; } for(int k = start; k <= end; k++) { vector<TreeNode *> left = generate(start, k-1); vector<TreeNode *> right = generate(k+1, end); for(auto i: left) { for(auto j: right) { TreeNode *node = new TreeNode(k); node->left = i; node->right = j; result.push_back(node); } } } return result; } };
|
相关问题