96. 不同的二叉搜索树

题目链接

解题思路

• 暴力怎么做？n个节点，我们要先选头节点i，头节点选中之后，左子树的节点数就决定了，右子树的节点数也就决定了，所以选择头节点i后，不同的数目是左子树不同数目 * 右子树不同数目，这又是子问题了，又可以递归得到结果。

  • 有一个细节，假设n等于5，1，2，3，4，5，假设现在选择了3为头节点，右子树不同数目有多少个？其实右子树我并不用传入4，5这两个参数，我直接传入2，代表的是右子树有两个节点，一共有多少种不同的数目。

• 递归只有一个参数，直接加缓存就可以了

代码

class Solution {
public:
    // 一共有n个节点，一共有多少种不同的搜索二叉树？
    int process(int n, vector<int> &dp) {
        if (n <= 1) {   //   只有一个节点，或者没有节点了  只有一种树
            return 1;
        }
        if (dp[n] != -1) {
            return dp[n];
        }
        int ans = 0;
        // 谁做头？
        for (int i = 1; i <= n; ++i) {
            ans += process(i - 1, dp) * process(n - i, dp);
        }
        dp[n] = ans;
        return ans;
    }

    int numTrees(int n) {
        vector<int> dp(n + 1, -1);
        return process(n, dp);
    }
};