Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.
Example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
|
Constraints:
递归
首先, 和leetcode 96一样, 要先选取根节点. 根节点选定了, 所有的组合方式也就确定了.
举例 input = 6, 那么我们需要在(1,2,3,4,5,6)中选一个作为根节点. 不妨假设我们选择3作为根节点.
那么左子树就需要找到(1,2)对应的所有BST, 右子树就需要找到(4,5,6)对应的所有BST.
左子树好说, 就是generateTrees(2)返回的所有值.
**对于右子树, (4,5,6)构成的所有的BST形状上和(1,2,3)对应的所有BST一样, 只不过每个节点都加了3. **
也就是说, 找到了generateTrees(3)返回的所有子树的所有节点都加3, 就变成了所有右子树的BST.
那么我们新构造一个函数List<TreeNode> generateTrees(int n, int base), base是构造出从1到n的所有可能子树之后每个节点都加上base之后的所有子树.
对于根节点3, 所有的可能方式就是generateTrees(2, 0)和generateTrees(3, 3)两者组合一下的结果.
然后遍历根节点, 从1到6, 就找出所有可能方式了.
计算的过程中发现了很多重复计算, 比如计算generateTrees(5), 当选取3为根节点时, 要计算generateTrees(2, 0)和generateTrees(2, 2). 这两个返回的结果形状上完全一样, 只不过后一个每一个节点都比前一个对应的节点多了2.
所以可以不用递归, 打表储存从1到i的所有BST的形状即可, dp[i] = generateTrees(i) 用到的时候拿出来再在每个节点上加上base即可.
但是他给的这个TreeNode类没有实现clone()方法, 所以就没有试.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
class Solution {
public List<TreeNode> generateTrees(int n) {
if(n == 0)
return new ArrayList<TreeNode>();
return generateTrees(n, 0);
}
private List<TreeNode> generateTrees(int n, int base)
{
List<TreeNode> trees = new ArrayList<>();
if(n == 0)
{
trees.add(null);
return trees;
}
if(n == 1)
{
trees.add(new TreeNode(1 + base));
return trees;
}
for(int i = 1; i <= n; ++i)
{
List<TreeNode> leftTrees = generateTrees(i - 1, 0 + base);
List<TreeNode> rightTrees = generateTrees(n - i, i + base);
for(TreeNode leftTree : leftTrees)
{
for(TreeNode rightTree : rightTrees)
{
TreeNode rootWithi = new TreeNode(i + base);
rootWithi.left = leftTree;
rootWithi.right = rightTree;
trees.add(rootWithi);
}
}
}
return trees;
}
}
|