Unique Binary Search Trees II - LeetCode
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Unique Binary Search Trees II - LeetCode,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1225字,纯文字阅读大概需要2分钟。
内容图文
![Unique Binary Search Trees II - LeetCode](/upload/InfoBanner/zyjiaocheng/1108/0fecf068e14c47f3aa0f286aebc273fa.jpg)
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
思路:通过递归实现。我们设置一个生成节点编号st到ed的子树的递归函数,对于给定的st到ed,我们枚举中间的每一个数当作root节点,假设数为i,则继续调用参数为st到i-1以及i+1到ed的该函数生成所有左孩子和右孩子子树。
1
/*
*
2
* Definition for a binary tree node.
3
* struct TreeNode {
4
* int val;
5
* TreeNode *left;
6
* TreeNode *right;
7
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
* };
9
*/
10
class
Solution {
11
public
:
12 vector<TreeNode*> generateTrees(int n) {
13return gen_sub(1, n);
14 }
15 vector<TreeNode*> gen_sub(int st, int ed)
16 {
17 vector<TreeNode*> res;
18if (st > ed)
19 res.push_back(NULL);
20for (int i = st; i <= ed; i++)
21 {
22 vector<TreeNode*> lnodes = gen_sub(st, i - 1);
23 vector<TreeNode*> rnodes = gen_sub(i + 1, ed);
24for (TreeNode *ln : lnodes)
25for (TreeNode *rn : rnodes)
26 {
27 TreeNode *root = new TreeNode(i);
28 root->left = ln;
29 root->right = rn;
30 res.push_back(root);
31 }
32 }
33return res;
34 }
35 };
原文:http://www.cnblogs.com/fenshen371/p/4951777.html
内容总结
以上是互联网集市为您收集整理的Unique Binary Search Trees II - LeetCode全部内容,希望文章能够帮你解决Unique Binary Search Trees II - LeetCode所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。