不同的二叉搜索树

@[toc]

一、问题描述

二、分析

•  在已知前n-1个数的二叉搜索树数目后，插入第n个数，有哪些情况？
•  1.第n个数做根节点，前n-1个数形成其左子树，右子树为0个数，dp[n-1]*dp[0]种
•  2.第n-1个数做根节点，左子树为前n-2个数，右子树为第n个数，dp[n-2]*dp[1]种
•  ...
•  n-i+1.第i个数做根节点，左子树为前i-1个数，右子树为后n-i个数，dp[i-1]*dp[n-i]种
•  ...n.第1个数做根节点，左子树为0个数，右子树为后n-1个数，dp[0]*dp[n-1]种
•  我们将所有情况的二叉搜索树加起来即可

三、代码

class Solution {
public:
    int numTrees(int n) {
        // 二叉搜索数的特征，左子树小于根，右子树大于根
        vector<int> dp(n + 1, 0);
        // dp[0]初始化为1
        dp[0] = 1;  
        // 从1...n的二叉搜索数数目
        for(int i = 1; i <= n; i++)  
        	// 逐步选用1...n作为根节点
            for(int j = 1; j <= i; j++)  
            	// 左侧j-1个数，右侧i-j个数
                dp[i] += dp[j - 1] * dp[i - j]; 
                 
        return dp[n]; 
    }
};

四、问题描述

五、分析

方法：递归

•  首先来计数需要构建的二叉树数量。可能的二叉搜素数数量是一个 卡特兰数。
•  我们跟随上文的逻辑，只是这次是构建具体的树，而不是计数。
•  我们从序列 1 ..n 中取出数字 i，作为当前树的树根。于是，剩余 i - 1 个元素可用于左子树，n - i 个元素用于右子树。
•  如 前文所述，这样会产生 G(i - 1) 种左子树 和 G(n - i) 种右子树，其中 G 是卡特兰数。
  
•  现在，我们对序列 1 ... i - 1 重复上述过程，以构建所有的左子树；然后对 i + 1 ... n 重复，以构建所有的右子树。
•  这样，我们就有了树根 i 和可能的左子树、右子树的列表。
•  最后一步，对两个列表循环，将左子树和右子树连接在根上。

六、代码

class Solution {
public:
    vector<TreeNode*> helper(int start,int end)
    {
        vector<TreeNode*> ret;
        if(start > end)
            ret.push_back(nullptr);
        
        // pick up a root
        for(int i = start;i <= end;i++)
        {
        	// 如果i被选为根，所有可能的左子树
            vector<TreeNode*> left = helper(start,i - 1);
            // 如果i被选为根，所有可能的右子树
            vector<TreeNode*> right = helper(i + 1,end);
            // 将左右树连接到根i
            for(auto l : left)
            {
                for(auto r : right)
                {
                    TreeNode* root = new TreeNode(i);
                    root -> left = l;
                    root -> right = r;
                    ret.push_back(root);
                }
            }
        }
        return ret;
    }
    
    vector<TreeNode*> generateTrees(int n) 
    {
        vector<TreeNode*> ret;
        if(n == 0)
            return ret;    
        ret = helper(1,n);
        return ret;
    }
};