共计 1217 个字符，预计需要花费 4 分钟才能阅读完成。
Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.
Example:
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
难度：medium
题目：给出整数 n，生成其所有可能 BST.
思路：递归，分别把 1 到 n 作为根结点，例如 i, 则 1 到 i - 1 作为左子树，i+ 1 到 n 作为右子树。
Runtime: 2 ms, faster than 89.21% of Java online submissions for Unique Binary Search Trees II.Memory Usage: 39.9 MB, less than 100.00% of Java online submissions for Unique Binary Search Trees II.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) {val = x;}
* }
*/
class Solution {
public List<TreeNode> generateTrees(int n) {
if (n <= 0) {
return new ArrayList<TreeNode>();
}
return generateTrees(1, n);
}
private List<TreeNode> generateTrees(int left, int right) {
if (left > right) {
List<TreeNode> treeNodes = new ArrayList<>();
treeNodes.add(null);
return treeNodes;
}
List<TreeNode> result = new ArrayList<>();
for (int i = left; i <= right; i++) {
List<TreeNode> leftList = generateTrees(left, i – 1);
List<TreeNode> rightList = generateTrees(i + 1, right);
for (TreeNode lChild: leftList) {
for (TreeNode rChild: rightList) {
TreeNode root = new TreeNode(i);
root.left = lChild;
root.right = rChild;
result.add(root);
}
}
}
return result;
}
}
