LeetCode OJ :Unique Binary Search Trees II(唯一二叉搜索树)
2024-08-31 08:44:07
题目如下所示:返回的结果是一个Node的Vector:
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
树节点的定义是下面这样的
/**
* Definition for a binary tree node.
* struct 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 createNode(, n);
} vector<TreeNode*> createNode(int start, int end)
{
vector<TreeNode*> result;
if(start > end){
result.push_back(NULL);
return result;
}
for(int i = start; i <= end; ++i){
vector<TreeNode*> leftNode = createNode(start, i - );
vector<TreeNode*> rightNode = createNode(i + , end);
for(int j = ; j < leftNode.size(); ++j){
for(int k = ; k < rightNode.size(); ++k){
TreeNode * tmpNode = new TreeNode(i);
tmpNode->left = leftNode[j];
tmpNode->right = rightNode[k];
result.push_back(tmpNode);
}
}
}
return result;
}
};
这一题实际上更另外一个叫做different ways to add parentheses的题目比较相似,这个详见上一篇博文。
java版本的代码如下:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<TreeNode> generateTrees(int n) {
if(n == )//如果不加上这一条,当为0的时候会返回[[]],不知道为什么,很奇怪
return new ArrayList<TreeNode>();
return createTree(, n);
} public List<TreeNode> createTree(int start, int end){
ArrayList<TreeNode> result = new ArrayList<TreeNode>();
if(start > end){
result.add(null);
return result;
}
for(int i = start; i <= end; ++i){
for(TreeNode leftNode : createTree(start, i - )){
for(TreeNode rightNode : createTree(i + , end)){
TreeNode node = new TreeNode(i);
node.left = leftNode;
node.right = rightNode;
result.add(node);
}
}
}
return result;
}
}
最新文章
- IE10、IE11 User-Agent 导致的 ASP.Net 网站无法写入Cookie 问题
- Maven使用archetype迅速生成项目骨架
- [译]:Orchard入门——部件管理
- 图解:Arcgis Server 安装
- iOS中属性与成员变量的区别
- pageContext对象的用法
- 普通SQL语句可以用Exec执行
- Web 技术人员需知的Web 缓存知识
- ionic+angulajs
- SQL函数:小写金额转换成大写
- activitie用户手册
- UISearchDisplayController简单使用
- 剑指Offer——联通研究院笔、面试题 (Offer已收割)
- (六十三)自定义TabBar和TabBarButtonItem
- ccf 目录格式转换
- nginx实现https网站设置
- task打印执行结果
- 利用WindowsServiceWrapper(WinSW)将nginx包装为系统服务
- [转帖]批处理-For详解
- SpaceNet 数据集
热门文章
- Spring的IoC模式
- alter session set events
- iOS学习之移除Main.storyboard
- Python(输入、输出;简单运算符;流程控制;转译)
- Spark机器学习8&#183; 文本处理(spark-shell)
- ASP.NET MVC 4.0 中使用NPOI 2.2.0 按模板生成Excel报表
- 检索并打印一个DNS主机条目
- QT添加资源文件,并为工具栏添加图片
- JAVA基础补漏--继承
- BZOJ4487 [Jsoi2015]染色问题