不同的二叉搜索树(二)

C++ 解法, 执行用时: 29ms, 内存消耗: 4100KB, 提交时间: 2022-04-27

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return TreeNode类vector
     */
    vector<TreeNode*> BSTgenerate(int n) {
        // write code here
        return dfs(n, 1);
    }
    vector<TreeNode*> dfs(int n, int start) {
        vector<TreeNode*> res;
        if (start > n) {
            res.push_back(nullptr);
            return res;
        }
        if (start == n) {
            TreeNode* node = new TreeNode(n);
            res.push_back(node);
            return res;
        }
        for (int i = start; i <= n; i++) {
            vector<TreeNode*> left = dfs(i - 1, start);
            vector<TreeNode*> right = dfs(n, i + 1);
            for (int j = 0; j < left.size(); j++) {
                for (int k = 0; k < right.size(); k++) {
                    TreeNode* tmp = new TreeNode(i);
                    tmp -> left = left[j];
                    tmp -> right = right[k];
                    res.push_back(tmp);
                }
            }
        }
        return res;
    }
};

C++ 解法, 执行用时: 30ms, 内存消耗: 4056KB, 提交时间: 2022-08-01

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return TreeNode类vector
     */
    
    vector<TreeNode*> BSTgenerate(int n) {
        // write code here
         if(n == 0)
        {
            return {};
        }
        return generateTrees(1,n);
    }
    vector<TreeNode*> generateTrees(int start,int end)
    {
        if(start > end)
        {
            return {nullptr};
        }
        vector<TreeNode*> allTrees;
        for(int i = start;i<=end;i++)
        {
            vector<TreeNode*> leftTrees = generateTrees(start, i-1);
            vector<TreeNode*> rightTrees = generateTrees(i+1, end);
            for(auto left : leftTrees)
            {
                for(auto right : rightTrees)
                {
                    TreeNode* curTree = new TreeNode(i);
                    curTree->left = left;
                    curTree->right = right;
                    allTrees.emplace_back(curTree);
                }
            }
        }
        return allTrees;
    }
};

C++ 解法, 执行用时: 30ms, 内存消耗: 4084KB, 提交时间: 2022-04-22

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return TreeNode类vector
     */
    vector<TreeNode*> dfs(int n, int start) {
        vector<TreeNode*> res;
        if (start > n) {
            res.push_back(NULL);
            return res;
        }
        if (start == n) {
            res.push_back(new TreeNode(n));
            return res;
        }
        for (int i = start; i <= n; i++) {
            vector<TreeNode*> left = dfs(i - 1,start);
            vector<TreeNode*> right = dfs(n, i + 1);
            for (int j = 0; j < left.size(); j++) {
                for (int k = 0; k < right.size(); k++) {
                    TreeNode* temp = new TreeNode(i);
                    temp->left = left[j];
                    temp->right = right[k];
                    res.push_back(temp);
                }
            }
        }
        return res;
    }
    vector<TreeNode*> BSTgenerate(int n) {
        // write code here
        return dfs(n, 1);
    }
};

C++ 解法, 执行用时: 31ms, 内存消耗: 4096KB, 提交时间: 2022-08-06

class Solution {
  public:
    vector<TreeNode*> BSTgenerate(int n) {
        return v(n, 1);
    }
    vector<TreeNode*> v(int n, int start) {
        vector<TreeNode*> z;
        if (start > n) {
            z.push_back(nullptr);
            return z;
        }
        if (start == n) {
            TreeNode* node = new TreeNode(n);
            z.push_back(node);
            return z;
        }
        for (int i = start; i <= n; i++) {
            vector<TreeNode*> L = v(i - 1, start);
            vector<TreeNode*> R = v(n, i + 1);
            
            for (int j = 0; j < L.size(); j++) {
                for (int k = 0; k < R.size(); k++) {
                    TreeNode* t = new TreeNode(i);
                    t -> left = L[j];
                    t -> right = R[k];
                    z.push_back(t);
                }
            }
        }
        return z;
    }
};

C++ 解法, 执行用时: 32ms, 内存消耗: 4136KB, 提交时间: 2022-07-28

static const auto io_sync_off = [](){
    std::ios::sync_with_stdio(false);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    vector<TreeNode*>dfs(int n,int start)
    {
        vector<TreeNode*>res;
        if (start > n) 
            return {nullptr};
        if (start == n) 
        {
            TreeNode* node = new TreeNode(n);
            res.push_back(node);
            return res;
        }
        for(int i=start;i<=n;i++)
        {
            vector<TreeNode*>left=dfs(i-1,start);
            vector<TreeNode*>right=dfs(n,i+1);
            for(int j=0;j<left.size();j++)
            {
                for(int k=0;k<right.size();k++)
                {
                    TreeNode* temp=new TreeNode(i);
                    temp->left=left[j];
                    temp->right=right[k];
                    res.push_back(temp);
                }
            }
        }
        return res;
    }
    vector<TreeNode*> BSTgenerate(int n) {
        return dfs(n,1);
    }
};

详情