这是LeetCode第95、96题

不同二叉搜索树的种类

首先是研究二叉搜索树的数量性质：

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

二叉搜索树，指对于根节点，左子树所有元素均小于该节点，右子树所有节点都大于这个节点。

例如，当n=1，显然只有一种情况。而当n=2，就有2种情况，这是因为1、2都可以作为根节点，产生2个不同的树。

特别地，当n=0也是一种情况，我们把NULL也看作一棵树。

接下来考虑n=3，它的根节点可以是1、2、3。从二叉搜索树性质出发：

  • 当根节点为1，它不会有左子树，而右子树有两个节点。
  • 当根节点为2，它一定有左右子树，而且各有一个节点。
  • 当根节点为3，情况与1类似。

这样，就找到了一个子问题。例如，当根节点为1，它的子问题就是：没有节点的二叉搜索树有几种情况，有2个节点的二叉搜索树有几种情况。

推广到一般情况并以此列出方程：
$$
dp[i] = \sum_{j=0}^{i-1}dp[j]dp[i-j-1]
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(23, 0);
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 5;
        for(int i = 4; i <= 19; i++){
            for(int j = 0; j <= i-1; j++){
                dp[i] += dp[j]*dp[i-j-1];
            }
        }
        return dp[n];
    }
};

列出所有不同的二叉搜索树

列出具体的二叉树，它们的头节点构成了一个vector。

1
2
3
4
5
6
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

采用区间表示：定义$(left, right)$ 表示一棵起于$left$，终于$right$的二叉搜索树。

此时类似前一题的问题：头节点下接两棵子树，显然，对于一个根节点值为$i$的树，左边应该是由$[left, i-1]$构成的，而右边是由$[i+1, right]$构成的。

思考：递推关系和返回值应该是什么？

假定有一个函数$dfs(left,right)$用于构造如上述的树，那么在$left = right$时，它应该是一个节点；在$left>right$时，它应该是空的。在$left<right$时，它是一棵树.

*因为是一棵树，所以返回类型应该是TreeNode**吗？

再回到构造过程以及题目，题目要求返回的是一个vector<TreeNode*>，它代表着树的集合。

而子问题：左右子树，它们同样是树的集合。

对于一个节点，它的左右子树都是一个集合，代表着不同情况的所有树，因此返回类型也应该是vector<TreeNode*>。特别地，对于$left=right$，它是一个只有一个节点的树，当$left>right$，它是一棵空的树。

值得一提的是，对于传入的left、right是区间，枚举其根节点（自身）还需要使用一个循环。

因此，构造的函数：

1
vector<TreeNode*> dfs(int left, int right);

边界条件：

1
2
3
if(left > right){
	return {nullptr};   // 注意：返回的是一个集合vector，{}不能省略
}

对于不同的根节点构造左右子树：

1
2
3
4
5
6
vector<TreeNode*> res; // result

for(int i = left; i <= right; i++){
    vector<TreeNode*> ltree = dfs(left, i-1);
	vector<TreeNode*> rtree = dfs(i+1, right);
}

遍历左右子树集合中的所有树，并保存在res中，注：这一段在循环内：

1
2
3
4
5
6
7
8
for(auto &l: ltree){
    for(auto &r: rtree){
        TreeNode* node = new(TreeNode);
        node->val = i;
        node->left = l;   // 当前节点的左子树是l，注意tree vector中虽然是节点，但实际上代表着一棵棵树
        node->right = r;
    }
}

再返回res即可。完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<TreeNode*> dfs(int left, int right){
    if(left > right){
        return {nullptr};   // 注意：返回的是一个集合vector，{}不能省略
    }
	vector<TreeNode*> res; // result

    for(int i = left; i <= right; i++){
        vector<TreeNode*> ltree = dfs(left, i-1);
        vector<TreeNode*> rtree = dfs(i+1, right);
        for(auto &l: ltree){
            for(auto &r: rtree){
                TreeNode* node = new(TreeNode);
                node->val = i;
                node->left = l;   // 当前节点的左子树是l，注意tree vector中虽然是节点，但实际上代表着一棵棵树
                node->right = r;
            }
        }
    }
    return res;
}

vector<TreeNode*> generateTrees(int n) {
    return dfs(1, n);
}

关于C++为什么应该使用nullptr而不是NULL，是因为在C语言中，NULL是可以被强制类型转换的。