题目描述
给定一个整数 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
思路：
这个问题可以划分为已每一个节点为根节点时的树集合，当以某一个节点为根节点时，情况可以是左右子树两两组合，即情况数为左子树数量乘以右子树数量的乘积。构造好之后就返回列表。同时左子树与右子树也要满足这样的情况。
代码：
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; left = null; right = null; }
* }
*/
import java.util.ArrayList;
public class Solution {
public ArrayList<TreeNode> generateTrees(int n) {
return createTrees(1, n);
}
private ArrayList<TreeNode> createTrees(int low, int high){
ArrayList<TreeNode> res = new ArrayList();
// 如果没有子节点了，加入null节点，返回列表
if (low > high){
res.add(null);
return res;
}
for (int i=low; i<=high; i++){
// 左右子树的列表
ArrayList<TreeNode> leftTrees = createTrees(low, i-1);
ArrayList<TreeNode> rightTrees = createTrees(i+1, high);
// 两两组合
for (int j=0; j<leftTrees.size(); j++){
for (int k=0; k<rightTrees.size(); k++){
TreeNode root = new TreeNode(i);
// 接上之后放入列表
root.left = leftTrees.get(j);
root.right = rightTrees.get(k);
res.add(root);
}
}
}
return res;
}
}
