题目描述：
给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。
示例
输入：3
输出：
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释：
以上的输出对应以下 5 种不同结构的二叉搜索树：
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
0<=n<=8
我们可以利用一下查找二叉树的性质。左子树的所有值小于根节点，右子树的所有值大于根节点。
所以如果求 1...n 的所有可能。
我们只需要把 1 作为根节点，[ ] 空作为左子树，[ 2 ... n ] 的所有可能作为右子树。
2 作为根节点，[ 1 ] 作为左子树，[ 3...n ] 的所有可能作为右子树。
3 作为根节点，[ 1 2 ] 的所有可能作为左子树，[ 4 ... n ] 的所有可能作为右子树，然后左子树和右子树两两组合。
4 作为根节点，[ 1 2 3 ] 的所有可能作为左子树，[ 5 ... n ] 的所有可能作为右子树，然后左子树和右子树两两组合。
...
n 作为根节点，[ 1... n ] 的所有可能作为左子树，[ ] 作为右子树。
如果只有一个数字，那么所有可能就是一种情况，把该数字作为一棵树。而如果是 [ ]，那就返回 null。
这更像是分治法，把大问题拆分成多个小的子问题
既然是递归，那么一定会有一个程序的出口，对于此题来说，出口就是把多余的数添加到构建的查找二叉树中。
public List<TreeNode> generateTrees(int n) {
List<TreeNode> ans = new ArrayList<TreeNode>();
if (n == 0) {
return ans;
}
return getAns(1, n);
}
private List<TreeNode> getAns(int start, int end) {
List<TreeNode> ans = new ArrayList<TreeNode>();
//此时没有数字，将 null 加入结果中
if (start > end) {
ans.add(null);
return ans;
}
//只有一个数字，当前数字作为一棵树加入结果中
if (start == end) {
TreeNode tree = new TreeNode(start);
ans.add(tree);
return ans;
}
//尝试每个数字作为根节点
for (int i = start; i <= end; i++) {
//得到所有可能的左子树
List<TreeNode> leftTrees = getAns(start, i - 1);
//得到所有可能的右子树
List<TreeNode> rightTrees = getAns(i + 1, end);
//左子树右子树两两组合
for (TreeNode leftTree : leftTrees) {
for (TreeNode rightTree : rightTrees) {
TreeNode root = new TreeNode(i);
root.left = leftTree;
root.right = rightTree;
//加入到最终结果中
ans.add(root);
}
}
}
return ans;
}
动态规划
大多数递归都可以用动态规划的思想重写
举个例子，n = 3
数字个数是 0 的所有解
null
数字个数是 1 的所有解
1
2
3
数字个数是 2 的所有解，我们只需要考虑连续数字
[ 1 2 ]
1
\
2
2
/
1
[ 2 3 ]
2
\
3
3
/
2
如果求 3 个数字的所有情况。
[ 1 2 3 ]
利用解法二递归的思路，就是分别把每个数字作为根节点，然后考虑左子树和右子树的可能
1 作为根节点，左子树是 [] 的所有可能，右子树是 [ 2 3 ] 的所有可能，利用之前求出的结果进行组合。
1
/ \
null 2
\
3
1
/ \
null 3
/
2
2 作为根节点，左子树是 [ 1 ] 的所有可能，右子树是 [ 3 ] 的所有可能，利用之前求出的结果进行组合。
2
/ \
1 3
3 作为根节点，左子树是 [ 1 2 ] 的所有可能，右子树是 [] 的所有可能，利用之前求出的结果进行组合。
3
/ \
1 null
\
2
3
/ \
2 null
/
1
然后利用上边的思路基本上可以写代码了，就是求出长度为 1 的所有可能，长度为 2 的所有可能 ... 直到 n。
但是我们注意到，求长度为 2 的所有可能的时候，我们需要求 [ 1 2 ] 的所有可能，[ 2 3 ] 的所有可能，这只是 n = 3 的情况。如果 n 等于 100，我们需要求的更多了 [ 1 2 ] ， [ 2 3 ] ， [ 3 4 ] ... [ 99 100 ] 太多了。能不能优化呢？
仔细观察，我们可以发现长度是为 2 的所有可能其实只有两种结构。
x
/
y
y
\
x
看之前推导的 [ 1 2 ] 和 [ 2 3 ]，只是数字不一样，结构是完全一样的。
[ 1 2 ]
1
\
2
2
/
1
[ 2 3 ]
2
\
3
3
/
2
推广到任意长度 len，我们其实只需要求 [ 1 2 ... len ] 的所有情况就可以了。下一个问题随之而来，这些 [ 2 3 ] ， [ 3 4 ] ... [ 99 100 ] 没求的怎么办呢？
举个例子。n = 100，此时我们求把 98 作为根节点的所有情况，根据之前的推导，我们需要长度是 97 的 [ 1 2 ... 97 ] 的所有情况作为左子树，长度是 2 的 [ 99 100 ] 的所有情况作为右子树。
[ 1 2 ... 97 ] 的所有情况刚好是 [ 1 2 ... len ] ，已经求出来了。但 [ 99 100 ] 怎么办呢？我们只求了 [ 1 2 ] 的所有情况。答案很明显了，在 [ 1 2 ] 的所有情况每个数字加一个偏差 98，即加上根节点的值就可以了。
[ 1 2 ]
1
\
2
2
/
1
[ 99 100 ]
1 + 98
\
2 + 98
2 + 98
/
1 + 98
即
99
\
100
100
/
99
所以我们需要一个函数，实现树的复制并且加上偏差。
private TreeNode clone(TreeNode n, int offset) {
if (n == null) {
return null;
}
TreeNode node = new TreeNode(n.val + offset);
node.left = clone(n.left, offset);
node.right = clone(n.right, offset);
return node;
}
通过上边的所有分析，代码可以写了，总体思想就是求长度为 2 的所有情况，求长度为 3 的所有情况直到 n。而求长度为 len 的所有情况，我们只需要求出一个代表 [ 1 2 ... len ] 的所有情况，其他的话加上一个偏差，加上当前根节点即可。
public List<TreeNode> generateTrees(int n) {
ArrayList<TreeNode>[] dp = new ArrayList[n + 1];
dp[0] = new ArrayList<TreeNode>();
if (n == 0) {
return dp[0];
}
dp[0].add(null);
//长度为 1 到 n
for (int len = 1; len <= n; len++) {
dp[len] = new ArrayList<TreeNode>();
//将不同的数字作为根节点，只需要考虑到 len
for (int root = 1; root <= len; root++) {
int left = root - 1; //左子树的长度
int right = len - root; //右子树的长度
for (TreeNode leftTree : dp[left]) {
for (TreeNode rightTree : dp[right]) {
TreeNode treeRoot = new TreeNode(root);
treeRoot.left = leftTree;
//克隆右子树并且加上偏差
treeRoot.right = clone(rightTree, root);
dp[len].add(treeRoot);
}
}
}
}
return dp[n];
}
private TreeNode clone(TreeNode n, int offset) {
if (n == null) {
return null;
}
TreeNode node = new TreeNode(n.val + offset);
node.left = clone(n.left, offset);
node.right = clone(n.right, offset);
return node;
}
值得注意的是，所有的左子树我们没有 clone ，也就是很多子树被共享了，在内存中就会是下边的样子。
图片.png
也就是左子树用的都是之前的子树，没有开辟新的空间。
网友评论