不同的二叉搜索树

不同的二叉搜索树【中等题】

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

题目详解

首先想强调的一点，题意是二叉搜索树而不是二叉树，看到了这一点，这道题的题意也就了解了。其次我们要知道一棵二叉搜索树的子树依旧是二叉搜索树，明白这一点，我们就能把问题分解为子问题了。解这道题的思路大致如下：

1. 从1到n每一个数都可以作为根结点，所以肯定有一个循环
2. 循环中每选择一个i，都会把[1,n]的数组划分成两段，每一段都有自己的若干棵二叉搜索树，把这两个集合做一个笛卡尔积（即两两组合），就能得到最后的答案

晕了吗？没有晕的话就可以直接看代码了；晕了的话，我们再说的详细一点：

1. 选出根结点后应该先分别求解该根的左右子树集合，也就是根的左子树有若干种，它们组成左子树集合，根的右子树有若干种，它们组成右子树集合。
2. 然后将左右子树相互配对，每一个左子树都与所有右子树匹配，每一个右子树都与所有的左子树匹配。然后将两个子树插在根结点上。
3. 最后，把根结点放入链表中

现在大家都明白了这道题的思路，我们来看一下代码：

public List<TreeNode> generateTrees(int n) {
    if(n==0)
        return new ArrayList<>();
    return help(1,n);
}
List<TreeNode> help(int start,int end){
    List<TreeNode> list=new ArrayList<>();
    if(start>end){
        list.add(null);//这个容易忘记，不加的话下面会空指针异常
        return list;
    }
    for(int i=start;i<=end;i++){
        List<TreeNode> left=help(start,i-1);
        List<TreeNode> right=help(i+1,end);
        for(TreeNode l:left){
            for(TreeNode r:right){
                TreeNode root=new TreeNode(i);
                root.left=l;
                root.right=r;
                list.add(root);
            }
        }
    }
    return list;
}

代码最后两个for循环是整道题的逻辑核心，用来组合左右的二叉搜索树。

帮到你了的话，点一个在看吧♥◠‿◠ﾉ