题目

unique-binary-search-trees-ii

2. 算法

• 直接模拟

3. 代码

class Solution {

public:

    vector<TreeNode *> generateTrees(int n) {

        if (n == 0) return {};

        return *generateTreesDFS(1, n);

    }

    vector<TreeNode*> *generateTreesDFS(int start, int end) {

        vector<TreeNode*> *subTree = new vector<TreeNode*>();

        if (start > end) subTree->push_back(NULL);

        else {

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

                vector<TreeNode*> *leftSubTree = generateTreesDFS(start, i - 1);

                vector<TreeNode*> *rightSubTree = generateTreesDFS(i + 1, end);

                for (int j = 0; j < leftSubTree->size(); ++j) {

                    for (int k = 0; k < rightSubTree->size(); ++k) {

                        TreeNode *node = new TreeNode(i);

                        node->left = (*leftSubTree)[j];

                        node->right = (*rightSubTree)[k];

                        subTree->push_back(node);

                    }

                }

            }

        }

        return subTree;

    }

};