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

前言

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

一、不同的二叉搜索树

二、生成树+记忆搜索

1、递归回溯生成二叉树

// 不同的二叉搜索树。
public class NumTrees {
    
    /* target：给定节点个数，返回不同二叉搜索树的个数。 以每个节点为根节点，左右子树的个数相乘就是不同二叉树的个数。 自下而上，回溯生成树。 */
    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;
    }
}

2、记忆搜索–空间换时间

// 上面的方案超时，如果仅仅是得到不同二叉树个数，可以不用模拟每一次 区间生成子树，第一次生成后就将其记录，后面再碰到这个区间，直接取值即可。
class NumTrees2 {
    
    /* target：给定节点个数，返回不同二叉搜索树的个数。 以每个节点为根节点，左右子树的个数相乘就是不同二叉树的个数。 自下而上，回溯生成树。 用空间换时间，定义f[i][j]:[i,j]生成的子树有多少种可能，第一次就计算赋值，后面再碰到就不用算了，直接取出用即可。 */
    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 不同的二叉搜索树