95. Unique Binary Search Trees I

题目链接

https://leetcode.com/problems/unique-binary-search-trees-ii/

思路

区间的每个结点依次作为根，求出左右子树集合，进行组合

代码

class Solution {
public:
    vector<TreeNode*> dfs(int st, int ed) {
        if (st > ed) {
            return { NULL };
        }
        vector<TreeNode*> ans;

        for (int i = st; i <= ed; ++i) {
            //左右子树集合，进行组合
            vector<TreeNode*> left = dfs(st, i - 1);
            vector<TreeNode*> right = dfs(i + 1, ed);
            for (auto leftNode : left) {
                for (auto rightNode : right) {
                    TreeNode* root = new TreeNode(i);
                    root->left = leftNode;
                    root->right = rightNode;
                    ans.push_back(root);
                }
            }
        }
        return ans;
    }

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