[leetcode] 95. 不同的二叉搜索树 II

开始的想法是全排列数字1~n作为输入,然后构造BST,但是，不行，有重复。

下面代码是leetcode官方题解的C++版本
https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/bu-tong-de-er-cha-sou-suo-shu-ii-by-leetcode/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generate_trees(int start, int end)
    {
        vector<TreeNode*>all_trees;
        if(start > end)
        {
            all_trees.push_back(NULL);  //不能直接return all_trees;
        }
        //pick up i as root
        for(int i = start; i <= end; i++)
        {
            //得到所有可做为i左子树的子树根结点,[start,i - 1] < i
            vector<TreeNode*>left_trees = generate_trees(start, i - 1); 
            //得到所有可做为i右子树的子树根结点,[i + 1, end] > i
            vector<TreeNode*>right_trees = generate_trees(i + 1 , end);

            //笛卡儿积
            for(auto l: left_trees)
            {//开始那里直接return all_trees;的话这里就不循环了
                for(auto r: right_trees)
                {
                    TreeNode* root = new TreeNode(i);
                    root->left = l;
                    root->right = r;
                    all_trees.push_back(root);
                }
            }
        }
        return all_trees;
    }
    vector<TreeNode*> generateTrees(int n) {
        if(n == 0)
        {
            return vector<TreeNode*>(0);
        }
        return generate_trees(1, n);
    }
};

+备忘录：

参考：https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/jian-dan-yi-dong-cong-guan-fang-de-si-lu-zuo-liao-/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    map<pair<int,int>,vector<TreeNode*>>hash; //当备忘录
public:
    vector<TreeNode*> generate_trees(int start, int end)
    {
        vector<TreeNode*>all_trees;
        if(start > end)
        {
            all_trees.push_back(NULL);  //不能直接return all_trees;
        }
        pair<int, int>curKey(start, end);
        if(hash.find(curKey) != hash.end())
        { //之前递归得到过,所以不用算了，直接拷过去
            all_trees = hash[curKey];
        }
        else
        {
            //pick up i as root
            for(int i = start; i <= end; i++)
            {
                //得到所有可做为i左子树的子树根结点
                vector<TreeNode*>left_trees = generate_trees(start, i - 1); 
                //得到所有可做为i右子树的子树根结点
                vector<TreeNode*>right_trees = generate_trees(i + 1 , end);

                //笛卡儿积
                for(auto l: left_trees)
                {//开始那里直接return all_trees;的话这里就不循环了
                    for(auto r: right_trees)
                    {
                        TreeNode* root = new TreeNode(i);
                        root->left = l;
                        root->right = r;
                        all_trees.push_back(root);
                    }
                }
            }
            hash[curKey] = all_trees;
        }
        return all_trees;
    }
    vector<TreeNode*> generateTrees(int n) {
        if(n == 0)
        {
            return vector<TreeNode*>(0);
        }
        
        return generate_trees(1, n);
    }
};