LeetCode——不同的二叉搜索树II

NO.95 不同的二叉搜索树II 中等

本题和NO.96不同的二叉搜索树作为姊妹题，唯一的不同就是本题需要生成树的即可。而NO.96题只需要返回种类数量即可。

思路一：递归

在NO.95中进行过的这么一个例子：

​ n是4={“1作为根节点=左子树[1,0]*右子树[2,4]”+

​ “2作为根节点=左子树[1,1]*右子树[3,4]”+

​ “3做为根节点=左子树[1,2]*右子树[4,4]”+

​ “4作为根节点=左子树[1,3]*右子树[5,4]” }

这个形式就很”递归”！毕竟递归和动态规划之间一直都是藕断丝连的！

递归的过程：

1. 我们需要生成每个数字作为根节点时候的左右子树，得到左右子树的所有形式就可以轻松地组合得到整棵树。

2. 每个子树所包含的区间内的数字分别作为子树的根节点，得到子树根节点的左右子树的所有形式。。。

由此过程可知：这个生成bst的递归函数的参数需要的是数字区间，返回值是区间内数字所能组成的所有BST的集合List<TreeNode>。

递归的出口：当区间内只有一个数字，那么只有一种情况，该数字作为一棵树。当区间为空，就返回null。

public List<TreeNode> generateTrees(int n) {
    if (n==0)return new ArrayList<>();
    return buildBST(1,n);
}

private List<TreeNode> buildBST(int start, int end) {
    List<TreeNode> res=new ArrayList<>();
    //区间为空
    if (start > end) {
        res.add(null);
        return res;
    }
    //区间内只有一个数字
    if (start == end) {
        res.add(new TreeNode(start));
        return res;
    }
    //区间里有多个数字，每个数字分别作为根节点
    for (int i=start;i<=end;i++){
        //i作为根节点时所有的左子树
        List<TreeNode> leftList=buildBST(start,i-1);
        //i作为根节点时所有的右子树
        List<TreeNode> rightList=buildBST(i+1,end);
        //左右子树两两组合得到树
        for (TreeNode leftTree : leftList) {
            for (TreeNode rightTree : rightList) {
                //i作为根
                TreeNode root=new TreeNode(i);
                root.left=leftTree;
                root.right=rightTree;
                //保存
                res.add(root);
            }
        }
    }
    return res;
}

递归的复杂度好难算，要是简单的排列组合还在可控范围之内，直接套用排列组合公式。

关于本题时间复杂度的计算暂时搁浅了。

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github