95. 不同的二叉搜索树 II

BST性质

• left < root < right

• 中序遍历是非递减序列

  思路

• 这题是一个求方案数的题目， 一般想到回溯

• 难点在于左右子树的处理， 由于给定的是中序()， 实际上任意选择一个root, 都有对应的BST存在。

    function generateTrees(n: number): Array<TreeNode | null> {
        /* [start, end] */
        function dfs(start: number, end: number): Array<TreeNode | null> {
            // base case
            // 必须啊要null
            if (start > end) return [null];
            let trees: Array<TreeNode | null> = [];
            // make choices
            /* 选根节点, 没有产生对同级choice产生影响， 因此不用撤销*/
            for (let i = start; i <= end; i++) {
                let leftSet = dfs(start, i - 1);
                let rightSet = dfs(i + 1, end);
                // left
                for (let left of leftSet) {
                    for (let right of rightSet) {
                        let root = new TreeNode(i);
                        root.left = left;
                        root.right = right;
                        trees.push(root);
                    }
                }
            }
            return trees;
        }
        return dfs(1, n);
    }

namespace l96_1 {
    function numTrees(n: number): number {
        /* [start, end] */
        const memo: number[][] = new Array(n)
            .fill(0)
            .map(() => new Array(n).fill(-1));
        function dfs(start: number, end: number): number {
            // base case
            if (start > end) return 1;
            let trees: number = 0;
            // make choices
            /* 选根节点, 没有产生对同级choice产生影响， 因此不用撤销*/
            if (memo[start][end] !== -1) return memo[start][end];
            for (let i = start; i <= end; i++) {
                let leftSet = dfs(start, i - 1);
                let rightSet = dfs(i + 1, end);
                trees += leftSet * rightSet;
                // lef
            }
            memo[start][end] = trees;
            return trees;
        }
        dfs(0, n - 1);
        console.table(memo);
        return memo[0][n - 1];
    }
    console.log(numTrees(5));
}
namespace l96_2 {
    function numTrees(n: number): number {
        /*
         * state: dp[i][j] 表示区间[i, j]BST的方案
         * base case: dp[i][j]=1 , i===j
         * choice: dp[i][j] = SUM(f(i, j, k));f(i, j, k)表示， root = k 时的方案 ， i <= k <= j
         */
        const dp: number[][] = new Array(n)
            .fill(0)
            .map((item) => new Array(n).fill(0));
        for (let i = 0; i < n; i++) dp[i][i] = 1;
        for (let start = 1; start < n; start++) {
            for (let i = 0, j = start; j < n; i++, j++) {
                // 中心点枚举
                for (let k = i; k <= j; k++) {
                    dp[i][j] +=
                        (k !== i ? dp[i][k - 1] : 1) *
                        (k !== j ? dp[k + 1][j] : 1);
                }
            }
        }
        console.table(dp);
        // base case
        return dp[0][n - 1];
    }
    console.log(numTrees(5));
    /* [start, end] */
}
namespace l96_3 {
    function numTrees(n: number): number {
        /*
         * state: 长度为n的序列有dp[n]种方案
         * base case： dp[0] = 0 dp[1] = 1
         * dp[i] = sum(f(k, i))  1<=k<=i, f(k, i)为，以k为中心点， 长度为i的bst方案数
         * f(k, i) = dp[k-1]*dp[i - k]
         */
        const G = new Array(n + 1).fill(0);
        G[0] = 1;
        G[1] = 1;
        for (let i = 2; i <= n; ++i) {
            /* 枚举中心点 */
            for (let j = 1; j <= i; ++j) {
                G[i] += G[j - 1] * G[i - j];
            }
        }
        return G[n];
    }
    /* [start, end] */
}

• 区间长度相同， BST方案是一样的， 这也是个可以优化的地方
•