注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex95 Unique Binary Search Trees II  

2015-05-17 20:21:49|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
上一篇文章中ex96的加强版~~~输出那些个BST

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++的话可以用各种stl还有vector什么的,c里面全都得自己开空间啊~~~各种坑~~
这是第二题用c++的~~用c暂时还写不出来~~

class Solution {
public:
Solution(){};
vector<TreeNode *> generateTrees(int n) {
return createTree(1, n);
}

vector<TreeNode *> createTree(int start, int end)
{
vector<TreeNode *> results;
if (start>end)
{
results.push_back(NULL);
return results;
}

for (int k = start; k <= end; k++)
{
//确定root节点
vector<TreeNode *> left = createTree(start, k - 1);
vector<TreeNode *> right = createTree(k + 1, end);
for (int i = 0; i<left.size(); i++)
{
for (int j = 0; j<right.size(); j++)
{

TreeNode * root = new TreeNode(k);
//TreeNode * root = new TreeNode();
//root->val = k;
root->left = left[i];
root->right = right[j];
results.push_back(root);
}
}
}
return results;
}
};

补充,2015-5-19,重新用c实现了一下这个程序,不过没有办法控制root内循环内的size,只能开了一个很大的数组,不过在oj上还是过了,见c代码

struct TreeNode** reConstruct(int start,int end,int *size)
{
struct TreeNode** result = NULL;
if (start>= end)
{
result = (struct TreeNode**)malloc(1 * sizeof(struct TreeNode*));
size[0]++;
if (start > end)
{
result[0] = NULL; //最后一个数都没有了
}
else
{
result[0] = (struct TreeNode*)malloc(1 * sizeof(struct TreeNode));
result[0]->val = start;//只剩一个数字了
result[0]->left = NULL;
result[0]->right = NULL;
}

return result;
}
else
{
int k, i, j;

//首先,选一个k作为keyValue
int leftSize = 0,rightSize=0;

result = (struct TreeNode**)malloc(10000 * sizeof(struct TreeNode*));
//没有办法控制result的大小,所以提前开大一点儿
int count = 0;
for (k = start; k <= end; k++)
{
//会返回一堆可行的left和right;
leftSize = 0;
rightSize = 0;
struct TreeNode** left = reConstruct(start, k - 1, &leftSize);
//左边生成的集合

struct TreeNode** right = reConstruct(k + 1, end,&rightSize);
//右边生成的集合
for (i = 0; i < leftSize; i++)
{
for (j = 0; j < rightSize; j++)
{
struct TreeNode*root = (struct TreeNode*)malloc(1 * sizeof(struct TreeNode*));
root->val = k; //k为当前root
root->left = left[i];
root->right = right[j];
result[count] = root;
count++;
}
}
}
size[0] = count; //表示当前集合的大小
return result;
}
}

struct TreeNode** generateTrees(int n, int* returnSize) {
int count = 0;
struct TreeNode** root = reConstruct(1,n,&count);
returnSize[0] = count;
return root;
}

update java version 2015/12/7

import ht.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class UniqueBinarySearchTreesII {
public List<TreeNode> generateTrees(int n) {
return helper(n);
}
private List<TreeNode> helper(int n) {
if (n <=0) {
return new ArrayList<>();
}
return dfs(1, n);
}
private List<TreeNode> dfs(int start, int end) {
List<TreeNode> res = new ArrayList<>();
if (start > end) {
res.add(null);
}
for (int k = start; k <= end; ++k) {
List<TreeNode> left = dfs(start, k - 1);
List<TreeNode> right = dfs(k + 1, end);
for (TreeNode i:left) {
for (TreeNode j:right) {
TreeNode root = new TreeNode(k);
root.left = i;
root.right = j;
res.add(root);
}
}
}
return res;
}
}


  评论这张
 
阅读(12)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017