2021-11-16 leetcode动态规划 96.不同的二叉搜索树 c++

leetcode 96. 不同的二叉搜索树

二叉搜索树

一棵搜索二叉树的两种情况：
i) 空树
ii) 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值

已知有序序列 1⋯n，求可构建出的不同二叉搜索树的种数

求不同种类的二叉搜索树需要保证两个方面：二叉树的特性和不同搜索二叉树的唯一性

解释：
二叉树的特性：左子树结点值小于根结点值，右子树结点值大于根结点值；
唯一性：每个搜索二叉树都不一样

如何保证？
对于给定序列1…i…n：i作为根；序列1…(i-1）作为左子树；序列(i+1)…n 作为右子树；
小的值作为左子树，相对更大的值作为右子树，保证了二叉树的特性；遍历i，不同的i作为根结点，保证了唯一性。
再按照同样的方式递归构建左子树和右子树。

二叉树的特性

算法核心：动态规划

为求解状态转移方程，现定义两个函数：

G(n) : 序列长度为n的不同二叉搜索树的个数

F(i, n): 以i为根结点值，序列长度为n的不同二叉树的个数

由定义可知：

(1) 遍历所有根结点i，所得到的F(1, n), F(2, n) …F(n, n)加起来 == G(n)，即

(2)以i为根，以左子树序列构建后的左子树的数量为G(i - 1)，同理右子树的数量为G(n - i)

则，此时以i为根结点的不同的搜索二叉树的个数为

结合（1）（2）可得状态转移方程：

状态转移方程的初始化

序列长度为0，即空树的情况，G(0) == 1；
序列长度为1，G(1) == 1;
（这两种情况都只能分别得到一棵树）
注意：当i >= 2时，需要设定G[i]初始值为0，方便计算

过程
遍历序列长度1～n：在不同长度下，遍历根结点，通过状态转移方程得到不同序列长度的树的种树，并加起来。

class Solution {
public:
    int numTrees(int n) {
        vector G(n + 1, 0);
        G[0] = 1;
        G[1] = 1;
        for(int i = 2; i <= n; i++) {//遍历序列长度
            for(int j = 1; j <= i; j++) //遍历不同根结点
                G[i] += G[j - 1] * G[i - j];
        }
        return G[n];
    }
};