不同的二叉搜索樹[自下而上回溯生成樹+記憶搜索--空間換時間]

前言

第一，對於二叉樹的生成，一般自上而下遞歸確定好子樹區間，自下而上回溯拼接生成樹。
第二，對於很多重複的計算，可以用額外的空間將其結果記住，以後再碰到就直接取即可，大大降低時間複雜度，一般就是指數級別的複雜度，特別需要這樣做。

一、不同的二叉搜索樹

二、生成樹+記憶搜索

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 不同的二叉搜索樹