95. 不同的二叉搜索树 II（分治）

95. 不同的二叉搜索树 II

• 题目
• 解题思路
• 代码

题目

给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。

提示：
0 <= n <= 8

解题思路

这题是96题的进化版，这次的主要思路是递归。
主要是：生成根，生成左子树，生成右子树，拼接。
还是和96由共同的思想：左子树的节点值的集合为 [1，i−1]，右子树的节点值的集合为 [i+1，n]

我们定义 helper(start, end) 函数表示当前值的集合为 [start,end]，
返回序列[start,end] 生成的所有可行的二叉搜索树。
我们考虑枚举[start,end] 中的值 i 为当前二叉搜索树的根，
那么序列划分为了[start,i−1] 和 [i+1,end] 两部分。
我们递归调用这两部分，即 helper(start, i - 1) 和 helper(i + 1, end)，
获得所有可行的左子树和可行的右子树，
那么最后一步我们只要从可行左子树集合中选一棵，再从可行右子树集合中选一棵拼接到根节点上，并将生成的二叉搜索树放入答案数组即可。

代码

class Solution {
        public List<TreeNode> generateTrees(int n) {

        if (n == 0) {
            return new ArrayList<>();//如果是0，直接返回一个空的子树
        }
        List<TreeNode> res = helper(1, n);//范围是从1到n
        return res;
    }

    public List<TreeNode> helper(int start, int end) {
        List<TreeNode> res = new ArrayList<>();

        if (start > end) {//边界条件：这种情况就是没有根节点的。
            res.add(null);
            return res;
        }

        for (int i = start; i <= end; i++) {//以i为根节点。
            List<TreeNode> leftChildren = helper(start, i - 1);//获得所有可行的左子树集合：i为根节点的左子树范围[1,i-1]
            List<TreeNode> rightChildren = helper(i + 1, end);//获得所有可行的右子树集合：i为根节点的左子树范围[i+1,end]

            // 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
            for (TreeNode left : leftChildren) {
                for (TreeNode right : rightChildren) {
                    TreeNode root = new TreeNode(i);//把i作为根节点
                    root.left = left;
                    root.right = right;
                    res.add(root);
                }

            }


        }
        return res;
    }

}