二叉搜索树第三期

如何计算所有合法的 BST。

01 不同的二叉搜索树

给你一个正整数，请你计算，存储 {1, 2, …, n} 这些值共有多少种不同的 BST 结构。

比如说输入 n = 3，算法返回 5，如图所示：

这是一个穷举问题。举个例子，比如给算法输入 n = 5，也就是用 {1，2，3，4，5} 这些数字去构造 BST。

首先，这棵 BST 的根节点总共有几种情况？

显然有 5 中情况，每个数字都可以作为根节点。

比如固定 3 为根节点，这个前提下能有几个不同的 BST？

根据 BST 的特性，根节点的左子树都比根节点的值小，右子树的值都比根节点的值大。

所以如果固定 3 为根节点，左子树节点就是 {1，2} 的组合，右子树就是 {4，5} 的组合。

左子树的组合数和右子树的组合数的乘积就是 3 作为根节点时的 BST 个数。

可以一眼看出 {1，2} 和 {4，5} 有几种组合，但是算法怎么设计。

只需要递归就可以了：

// 定义：闭区间[low, high] 的数字能组成 count(low, high) 中 BST
int count(int low, int high);

根据函数定义，结合刚才分析：

int count(int low, int high) {
    // base case
    if (low > high)
        return 1;
    int res = 0;
    for (int i = low; i <= high; ++i) {
        // i 的值作为根节点 root
        int left = count(low, i - 1);
        int right = count(i + 1, high);
        res += left * right;
    }
    return res;
}
// 主函数
int numTrees(int n) {
    return count(1, n);
}

注意 base case，当 low > high 闭区间 [low, high] 是个空区间，对应着空节点 nullptr，虽然是空节点，但是也是一种情况，所以返回 1。

待做：动态规划

02 不同的搜索二叉树 II

不止让你计算有多少个，而且让你构建所有合法的 BST。思路如下：

1. 穷举 root 节点所有可能；
2. 递归构造出左右子树的所有合法 BST；
3. 给 root 节点穷举所有左右子树的组合。

vector<TreeNode*> build(int low, int high) {
    vector<TreeNode*> res;
    // base case
    if (low > high) {
        res.push_back(nullptr);
        return res;
    }

    // 1. 穷举 root 节点所有可能
    for (int i = low; i <= high; ++i) {
        // 2. 递归构造出左右子树的所有合法 BST
        vector<TreeNode*> leftTree = build(low, i - 1);
        vector<TreeNode*> rightTree = build(i + 1, high);
        // 3. 给 root 节点穷举所有左右子树的组合
        for (TreeNode* left : leftTree) {
            for (TreeNode* right : rightTree) {
                // i 作为根节点 root 的值
                TreeNode* root = new TreeNode(i);
                root->left = left;
                root->right = right;
                res.push_back(root);
            }
        }
    }
    return root;
} 
// 主函数
vector<TreeNode*> generateTrees(int n) {
    if (n == 0) {
        return {};
    }
    return build(1)
}