Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.
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
题意:
给定n个节点,列举可形成的不同的BST集合
思路:
跟 [leetcode]96. Unique Binary Search Trees给定节点形成不同BST的个数 相似。
对于给定的n
需要去查[1, n]范围内可生成的BST,如下图,
1 1 2 3 3 ... i ... n
\ \ / \ / / / \
3 2 1 3 2 1 [1,i-1] [i+1,n]
/ \ / \
2 3 1 2
我们需要列出
以1为root可生成的所有BST
以2为root可生成的所有BST
......
那么对于任意以 i 为root可生成的所有BST,根据BST的性质:
其左子树的值一定小于i,也就是[1, i - 1]区间,用helper生成list of leftList
而右子树的值一定大于i,也就是[i + 1, n]区间, 用helper生成list of rightList
最后,用root, leftList中的值,rightList中的值,三者生成BST
代码:
class Solution {
public List<TreeNode> generateTrees(int n) {
if(n == 0) return new ArrayList<>();
return helper(1, n); // root node from 1 to n
} private List<TreeNode> helper(int left, int right){
List<TreeNode> result = new ArrayList<>();
if(left > right){
result.add (null);
return result;
}
for(int i = left; i <= right; i++){
List<TreeNode> lefts = helper(left, i-1);
List<TreeNode> rights = helper(i+1, right);
for(TreeNode l : lefts){
for(TreeNode r : rights){
TreeNode root = new TreeNode(i);
root.left = l;
root.right = r;
result.add(root);
}
}
}
return result;
}
}