首页 > 代码库 > [leetcode]Unique Binary Search Trees II
[leetcode]Unique Binary Search Trees II
问题描述:
Given n, generate all structurally uniqueBST‘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
confused what "{1,#,2,3}"
means?> read more on how binary tree is serialized on OJ.
基本思想:
参考
《Unique Binary Search Trees》 采用动态规划的方法从小到大的获得节点数对应的不同BST。 对于n+1个节点的tree 完全可以利用n个节点以下的BST信息获得。
代码:
TreeNode* IncreaseK(TreeNode * head,int k){ if(head == NULL) return NULL; TreeNode* newhead = new TreeNode(head->val+k); TreeNode* left = IncreaseK(head->left,k); TreeNode* right = IncreaseK(head->right,k); newhead->left = left; newhead->right = right; return newhead; } vector<TreeNode *> generateTrees(int n) { map<int , vector<TreeNode*> > myMap; vector<TreeNode *> result(1); if(n == 0) return result; TreeNode * head1 = new TreeNode(1); vector<TreeNode*> vec; vec.push_back(head1); myMap.insert(make_pair(1,vec)); for(int i = 2; i <=n; i++) { int k; //leftnode vector<TreeNode* > tmpvec; for(k = 0; k < i; k++) { vector<TreeNode* > leftvec; vector<TreeNode* > rightvec; //case 1: if(k == 0) { rightvec = myMap[i-1]; for(int pos = 0; pos < rightvec.size(); pos++) { TreeNode *tmphead = new TreeNode(k+1); TreeNode *right = IncreaseK(rightvec[pos],k+1); tmphead->right = right; tmpvec.push_back(tmphead); } } //case 2: else if(k == i-1) { leftvec = myMap[i-1]; for(int pos = 0; pos < leftvec.size(); pos++) { TreeNode *tmphead = new TreeNode(k+1); tmphead->left = leftvec[pos]; tmpvec.push_back(tmphead); } } //case 3: else { leftvec = myMap[k]; rightvec = myMap[i-1-k]; for(int lpos = 0; lpos < leftvec.size(); lpos++) { for(int rpos =0; rpos < rightvec.size(); rpos++) { TreeNode *tmphead = new TreeNode(k+1); tmphead->left = leftvec[lpos]; TreeNode *right = IncreaseK(rightvec[rpos],k+1); tmphead->right = right; tmpvec.push_back(tmphead); } } } } myMap.insert(make_pair(i,tmpvec)); } return myMap[n]; }
[leetcode]Unique Binary Search Trees II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。