leetcode做题笔记95. 不同的二叉搜索树 II-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode做题笔记95. 不同的二叉搜索树 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

思路一：递归

struct TreeNode ** partition(int start, int end, int* returnSize){
    *returnSize = 0;
    int size = 32;
    struct TreeNode** ans = malloc(sizeof(struct TreeNode*) * size);
    if (start >= end) {
        ans[0] = NULL;
        *returnSize = 1;
        return ans;
    }
    for (int i = start; i < end; i++) {
        int lsize, rsize;
        struct TreeNode** lnode = partition(start, i, &lsize);
        struct TreeNode** rnode = partition(i + 1, end, &rsize);
        for (int m = 0; m < lsize; m++) {
            for (int n = 0; n < rsize; n++) {
                if (*returnSize >= size) {
                    size <<= 1;
                    ans = realloc(ans, sizeof(struct TreeNode*) * size);
                }
                int index = (*returnSize)++;
                ans[index] = malloc(sizeof(struct TreeNode));
                ans[index]->left = lnode[m];
                ans[index]->right = rnode[n];
                ans[index]->val = i + 1;
            }
        }
        free(lnode);
        free(rnode);
    }
    return ans;
}

struct TreeNode** generateTrees(int n, int* returnSize){
    struct TreeNode** ans = partition(0, n, returnSize);
    return ans;
}