不同的二叉搜索树[自下而上回溯生成树+记忆搜索--空间换时间]

• 前言
• 一、不同的二叉搜索树
• 二、生成树+记忆搜索
• • 1、递归回溯生成二叉树
  • 2、记忆搜索--空间换时间
• 总结
• 参考文献

第一，对于二叉树的生成，一般自上而下递归确定好子树区间，自下而上回溯拼接生成树。
第二，对于很多重复的计算，可以用额外的空间将其结果记住，以后再碰到就直接取即可，大大降低时间复杂度，一般就是指数级别的复杂度，特别需要这样做。

// 不同的二叉搜索树。
public class NumTrees {
    
    public int numTrees(int n) {
        return numTrees(1, n);
    }

    // 自下而上，回溯生成。
    private int numTrees(int begin, int end) {
        // 无法再进行划分，返回左孩子的个数，1个null节点。
        if (begin > end) return 1;
        // 得到左右孩子的组合数。
        int rs = 0;
        for (int i = begin; i <= end; i++) {
            // i作为根节点，划分两个区间，分别作为左右子树。
            rs += numTrees(begin, i - 1) * numTrees(i + 1, end);
        }
        return rs;
    }
}

// 上面的方案超时，如果仅仅是得到不同二叉树个数，可以不用模拟每一次 区间生成子树，第一次生成后就将其记录，后面再碰到这个区间，直接取值即可。
class NumTrees2 {
    
    public int numTrees(int n) {
        // 定义[i,j]能生成多少子树。
        int[][] f = new int[n + 1][n + 1];
        // 自下而上，回溯生成。
        return numTrees(1, n, f);
    }

    // 自下而上，回溯生成。
    private int numTrees(int begin, int end, int[][] f) {
        // 无法再进行划分，返回左孩子的个数，1个null节点。
        if (begin > end) return 1;
        // 记忆搜索
        if (f[begin][end] != 0) return f[begin][end];
        // 得到左右孩子的组合数。
        // 第一次碰到这个区间，其得到的结果记住。
        for (int i = begin; i <= end; i++) {
            // i作为根节点，划分两个区间，分别作为左右子树。
            f[begin][end] += numTrees(begin, i - 1, f) * numTrees(i + 1, end, f);
        }
        // 返回该区间第一次计算得到的子树个数。
        return f[begin][end];
    }
}

1）如何生成一颗二叉树，自上而下递归划分左右区间，自下而上回溯拼接左右子树。
2）记忆搜索用于避免重复计算，降低时间复杂度，尤其是指数级时间复杂度。

[1] LeetCode 不同的二叉搜索树