c++ - 查找所有唯一二叉搜索树的算法的时间复杂度是多少？

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <vector>
using namespace std;

class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
        vector<TreeNode *> list;

        // Input validation.
        if (n <= 0) {
            list.push_back(NULL);
            return list;
        }

        int left = 1;
        int right = n;
        generateTrees(left, right, list);

        return list;
    }

    void generateTrees(int left, int right, vector<TreeNode *> &list) {
        // Base case.
        if (left > right) {
            list.push_back(NULL);
            return;
        }

        for (int i = left; i <= right; i ++) {
            vector<TreeNode *> left_trees;
            generateTrees(left, i - 1, left_trees);

            vector<TreeNode *> right_trees;
            generateTrees(i + 1, right, right_trees);

            for (vector<TreeNode *>::iterator left_it = left_trees.begin();
                 left_it != left_trees.end(); left_it ++) {

                TreeNode *leftTree = *left_it;

                for (vector<TreeNode *>::iterator right_it = right_trees.begin();
                     right_it != right_trees.end(); right_it ++) {

                    TreeNode *rightTree = *right_it;

                    TreeNode *root = new TreeNode(i);
                    root->left = leftTree;
                    root->right = rightTree;

                    list.push_back(root);
                }
            }
        }
    }
};

最佳答案

给定n个节点，二叉搜索树的总数是加泰罗尼亚数，请引用这个链接:http://en.wikipedia.org/wiki/Catalan_number。所以，时间复杂度也是 O(Catalan(n))。

关于c++ - 查找所有唯一二叉搜索树的算法的时间复杂度是多少？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24618084/