写在前面

二叉搜索树的题一定要利用二叉搜索树的特性：中序遍历特性、任意节点左子树都小于根节点，右子树大于根节点。

主要分为三个部分：

  • 从最基本搜索树数目到具体的树结构：递归的思路
  • 利用memo来优化代码，加快整体速度（static变量设置）
  • 动态规划的实现方法

二叉搜索树的种类

不要求输出具体结果，比较容易思考，考虑一个节点它需要做什么？如何获取以它为根节点的二叉搜索树种类？

  • 考虑一个节点的二叉搜索树数目
    • 左边可能情况乘以右边的可能情况
    • 递归计算下去
  • 特殊性
    • 只考虑节点数目：【1,3】与【4,6】能构成的二叉搜索树的数目是相同的，只不过元素值不同而已，所以只要考虑构造二叉搜索树的节点数目即可。
    • 另外构造过程具有一定的对称性，以【1,4】举例，节点1和节点4分别为根节点的二叉搜索树数目是一致的；同时要考虑总节点数目为奇数的情况。

  • 注意点

    • 对于只有一个节点或者没有节点的情况，对应的二叉搜索树数目都是1.

      class Solution {
public:
int numTrees(int n) {
if(n==1 || n==0)  // 只有一个节点或者没有节点算是一种情况
    return 1;
int nums=0;
for(int i=1;i<=n/2;i++) {
    int left=numTrees(i-1);
    int right=numTrees(n-i);
    nums+=left*right;
}
nums*=2;    // 情况是对称的
if(n%2==1) {
    int left=numTrees(n/2);
    nums+=left*left;
}
return nums;
}
};

具体的二搜索树结构

相比于只返回数目要难思考一些，整体思路大概明晰，感觉主要是一些函数返回值及具体实现需要着重思考。

  • 递归函数返回值
    • 返回值是vector<TreeNode*>里面是所有情况的根节点
  • 函数主体：
    • 思路应该是和上述计算总的数目类似，即组合当前节点的左右可能情况
  • 整体来看
    1. 返回值：更改int返回值为vector<TreeNode*>
    2. 传入的参数需要是一个范围，而不是数目，因为需要考虑具体节点
    3. 创建的nums改为vector<TreeNode*> res
    4. 终止条件：如果区间内没有数，则添加空指针并返回结果
    5. 组合所有情况：不是简单的左边乘以右边，而是需要依次组合左右子树可能的根节点并将这种情况结果插入res

  • 下面代码中所有的节点在新的树结构中都被创建了一次，因此不同的树之间是没有关联的

    class Solution {
public:
// 返回根节点即可
vector<TreeNode*> generateTrees(int n) {
    // if(n==0)
    return generate(1,n);
}
vector<TreeNode*> generate(int lo,int hi){
    vector<TreeNode*> res;
    // 边界不符
    if(lo>hi) {
        res.push_back(nullptr);
        return res;
    }
    //  1. 穷举 root 节点的所有可能
    for(int i=lo;i<=hi;i++) {
        // 递归生成左右左右可能的情况
        vector<TreeNode*> left=generate(lo,i-1);
        vector<TreeNode*> right=generate(i+1,hi);
        for(auto L:left) {
            for (auto R:right) {
                // 构建并连接左右子树
                res.push_back(new TreeNode(i,L,R));
            }
        }
    }
    // 这种方法生成的树结构整体是混乱的吗？
        // 不是的，每一次都是重新创建节点了
    return res;
}
};

利用memo记忆优化

这里优化是针对整体的计算而言的，例如对于求二叉搜索树数目单个示例而言，上述方法没有重复计算的地方；但是对于多个示例则肯定是有重复计算的地方。对于具体的树结构也是同样的道理。思路来源于题解评论区 。

  • 对于单个示例，每一种组合都需要计算一次，但是对于大量的示例来说就可以计算一次从而获取所有的组合情况。
  • 哈希表存储的数据：unordered_map<pair<int,int>,vector<TreeNode*>> mp;
  • 将其设置为静态变量

动态规划求数目思路

主要是递推公式的获取思路，最重要的部分

  • 递推公式的获取

首先，对于 $N$ 个结点，它所能构成的搜索二叉树是由 $1\sim N$ 中每个数字作为根节点的情况的总和。

记 $G(N)$ 为 $N$ 个结点所能构成的二叉搜索树情况，$F(i,N)$ 为 第 $i$ 个结点作为根节点时二叉搜索树的数目，则有

$$G(N)=\sum_{i=1}^{N}F(i,N)$$

最重要的部分：$F(i,N)$ 的数量是由什么决定的呢？

  1. 首先左子树，$i$ 为根节点的左边孩子都要小于 $i$，也就是由 $1\sim i-1$组成的二叉搜索树，这不就是 $G(i-1)$吗？
  2. 再者右子树，是由 $i+1\sim N$ 等数字组成的二叉搜索树，其实它的数目就是 $G(N-i)$，稍微思考下，$G(N)$ 和序列内容没有关系，只和序列长度有关
  3. 排列组合得到 $F(i,N)$ 的递推式： $F(i,N)=G(i-1)\dot G(N-i)$

结合以下，就有：

$$G(N)=\sum{i=1}^{N}F(i,N)=\sum{i=1}^{N}G(i-1)\dot G(N-i)$$

至此，递推式确定。

  • 递推公式初始化
  1. 考虑最简单的情况 $G(0)=0，G(1)=1$
  • 遍历顺序

由递推式可得，从前往后依次遍历即可。

$\cdots$ end $\cdots$