首页 > 代码库 > 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思路：使用递归来求解该问题。GenerateSub( start, end )生成[start,end]区间的所有二叉树。为了求解GenerateSub( start, end )，依次取i=start,start+1,...,end为根节点，则，其所有左子树由GenerateSub( start, i-1 )得到，所有右子树由GenerateSub( i+1, end )得到。
1 class Solution { 2 public: 3 vector<TreeNode*> generateTrees( int n ) { 4 return GenerateSub( 1, n ); 5 } 6 private: 7 vector<TreeNode*> GenerateSub( int start, int end ) { 8 vector<TreeNode*> roots; 9 if( start > end ) { roots.push_back( 0 ); }10 for( int i = start; i <= end; ++i ) {11 vector<TreeNode*> left = GenerateSub( start, i-1 );12 vector<TreeNode*> right = GenerateSub( i+1, end );13 for( auto left_iter = left.begin(); left_iter != left.end(); ++left_iter ) {14 for( auto right_iter = right.begin(); right_iter != right.end(); ++right_iter ) {15 TreeNode *treeNode = new TreeNode( i );16 treeNode->left = *left_iter;17 treeNode->right = *right_iter;18 roots.push_back( treeNode );19 }20 }21 }22 return roots;23 }24 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。