96. 不同的二叉搜索树

求1,2,…,n构成的二叉搜索树的数量，我们可以把1,2,…n分别作为根节点。

则对特定的根节点i，它的左子搜索树由1到i-1构成（能构建的左子搜索树种类有x种），右子搜索树由i+1到n构成（能构建的右子搜索树种类有y种）。则以i为根节点的搜索树种类有x*y种
累加各个根节点对应的结果，即为最后结果

方法1：递归

递归函数的含义：
- 因为左子树和右子树的问题类型是一样的，都是由一系列递增数据的节点构成搜索树（只是节点范围不同），比如1,2,3和5,6,7构成的二叉搜索树的数量是一样的。所以递归函数helper(int n)表示n个递增数据点构成的搜索树数量
base case：
- 当左子树为空，右子树有n-1个节点时，此时能构成1*y种。所以可以理解为当节点为空时，能构成1种搜索树；
- 因此，当n为0时（表示空节点），helper(int n)的结果为1
对于特定的根节点i，它的左边有i-1个节点（所以能构建helper(i-1)种左子搜索树），右边有n-i个节点（所以能构建helper(n-i)种右子搜索树）

根据递归函数的含义，我们把代码写为（注意这时会超时）：

class Solution {
public:
    int helper(int n) {
        if (n == 0) return 1; // base case
        int res = 0;
        for (int i = 1; i < n+1; ++i) {
            res += helper(i-1) * helper(n - i );
        }
        return res;
    }

    int numTrees(int n) {
        return helper(n);
    }
};

代码之所以会超时，是因为每次递归时都要计算helper()函数。所以为了减少计算量，我们可以把已经计算好的结果保存起来，在递归过程中，若某个结果已经知道，则直接返回该结果即可，不必继续递归下去。所以只需要在上面的基础上，增加这三行代码：

unordered_map<int, int> record; // 增加这一行：用一个字典保存结果.字典的键为n，值为helper(n)对应的结果
if (record.count(n)) return record[n]; // 增加这一行：如果这个结果已经保存了，则直接返回
record[n]=res; // 增加这一行：用于保存当前结果

修改以后，正确的代码如下：

class Solution {
public:
    unordered_map<int, int> record; // 增加这一行：用一个字典保存结果.字典的键为n，值为helper(n)对应的结果
    int helper(int n) {        
        if (n == 0) return 1; // base case        
        if (record.count(n)) return record[n]; // 增加这一行：如果这个结果已经保存了，则直接返回
        int res = 0;
        for (int i = 1; i < n+1; ++i) {
            res += helper(i-1) * helper(n - i ); // 左边返回的结果*右边返回的结果
        }
        record[n]=res; // 增加这一行：用于保存当前结果
        return res;
    }

    int numTrees(int n) {
        return helper(n);
    }
};

方法2：动态规划

类比递归函数的含义，我们可以把dp数组的含义表示为：把i个递增数据点构成的搜索树数量保存在dp[i]中
状态转移方程：当前的结果dp[i]=左子树结果dp[j]（其中0<=j<i）*右子树结果dp[i-j-1]
base case: dp[0]=1;

class Solution {
public:
    int numTrees(int n) {
        vector<int>dp(n+1,0);
        dp[0]=1;
        for (int i = 1; i < n+1; ++i) {
            for (int j = 0; j < i; ++j) {
                dp[i]+=dp[j]*dp[i-j-1]; // 左子树节点数量+右子树节点数量=i-1
            }
        }
        return dp[n];
    }
};

95. 不同的二叉搜索树 II

本题要求返回二叉搜索树的“样子”，则对特定的根节点i，它左边的节点范围为1到i-1，右边的节点范围为i+1到n。此时左右两边的问题类型是一样的，只是数据的范围不同。所以我们构造一个辅助的递归函数，该函数的参数中记录搜索树的节点范围

递归函数helper(int start, int end)的含义：返回start到end节点范围的二叉搜索树的“样子”。注意这个范围是闭区间
base case：在构建左右子树时，因为下面的代码会导致helper()的start>end，所以用if (start>end) return vector<TreeNode *>{nullptr}; 进行特判，这种情况表示左子树为空（或者右子树为空）

for (int i = start; i <= end; ++i) {
    vector < TreeNode * > left = helper(start, i - 1);
    vector < TreeNode * > right = helper(i + 1, end);
    ...
}

可以理解为后序遍历：对左子树做点什么，对右子树做点什么。然后根据这些结果，拼装当前根节点对应的二叉搜索树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode *> helper(int start, int end) {
        vector<TreeNode *> res;
        if (start>end) { // 递归结束的条件
             return vector<TreeNode *>{nullptr};
        }
        for (int i = start; i <= end; ++i) {
//            后序遍历：左
            vector < TreeNode * > left = helper(start, i - 1); // 左子树的样子
//            后序遍历：右
            vector < TreeNode * > right = helper(i + 1, end); // 右子树的样子
//            后序遍历：中
            for (auto &l:left) {
                for (auto &r:right) {
                    TreeNode *tmp = new TreeNode(i, l, r); // 根，左，右，构建当前的树
                    res.push_back(tmp);
                }
            }
        }
        return res;
    }

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

    }
};