95. 不同的二叉搜索树 II

题目链接：https://leetcode.cn/problems/unique-binary-search-trees-ii/

这题不会，直接看的题解。

/**
 * 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*> genTrees(int start, int end) {
        if (start > end) {
            return { nullptr };
        }
        vector<TreeNode*> res;
        for (int i = start; i <= end; i++) {
            vector<TreeNode*> leftTrees = genTrees(start, i - 1);
            vector<TreeNode*> rightTrees = genTrees(i + 1, end);

            for (auto &left : leftTrees) {
                for (auto &right : rightTrees) {
                    TreeNode* root = new TreeNode(i);
                    root->left = left;
                    root->right = right;
                    res.emplace_back(root);
                }
            }
        }
        return res;
    }

    vector<TreeNode*> generateTrees(int n) {
        if (n <= 0) {
            return {};
        }
        return genTrees(1, n);
    }
};

/**

* 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*> genTrees(int start, int end) {

if (start > end) {

return { nullptr };

}

vector<TreeNode*> res;

for (int i = start; i <= end; i++) {

vector<TreeNode*> leftTrees = genTrees(start, i - 1);

vector<TreeNode*> rightTrees = genTrees(i + 1, end);

for (auto &left : leftTrees) {

for (auto &right : rightTrees) {

TreeNode* root = new TreeNode(i);

root->left = left;

root->right = right;

res.emplace_back(root);

}

return res;

}

vector<TreeNode*> generateTrees(int n) {

if (n <= 0) {

return {};

}

return genTrees(1, n);

}

};