首页 > 代码库 > Unique Binary Search Trees II
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.
1 3 3 2 1 \ / / / \ 3 2 1 1 3 2 / / \ 2 1 2 3
思路是每次一次选取一个结点为根，然后递归求解左右子树的所有结果，最后根据左右子树的返回的所有子树，依次选取然后接上（每个左边的子树跟所有右边的子树匹配，而每个右边的子树也要跟所有的左边子树匹配，总共有左右子树数量的乘积种情况），构造好之后作为当前树的结果返回。
C++代码如下：
#include<iostream>#include<new>#include<vector>using namespace std;//Definition for binary treestruct TreeNode{ int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution{public: vector<TreeNode *> generateTrees(int n) { return generate(1,n); } vector<TreeNode *> generate(int start,int end) { vector<TreeNode *> ret; if(start>end) { ret.push_back(NULL); return ret; } if(start==end) { TreeNode *root=new TreeNode(start); ret.push_back(root); return ret; } int i=start; for(i=start;i<=end;i++) { vector<TreeNode *> leftTree=generate(start,i-1); vector<TreeNode *> rightTree=generate(i+1,end); for(size_t j=0;j<leftTree.size();j++) { for(size_t k=0;k<rightTree.size();k++) { TreeNode *root=new TreeNode(i); root->left=leftTree[j]; root->right=rightTree[k]; ret.push_back(root); } } } return ret; }};int main(){ Solution s; vector<TreeNode*> vec=s.generateTrees(3); for(auto a:vec) cout<<a->val<<" "; cout<<endl;}
运行结果：
Unique Binary Search Trees II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。