# 95. Unique Binary Search Trees II

題目：<https://leetcode.com/problems/unique-binary-search-trees-ii/>

解法：遞迴法，題目要列出所有 binary search trees，所以要符合左子樹的值必須小於右子樹的值這個規則，所以遞迴的概念為從 1~n 取一個值當 root，接著列出小於它的所有 binary search trees，以及列出大於它的所有 binary search trees，然後建立左右子樹的所有排列組合即為答案

為實現使遞迴法，定義遞迴函數為 bst(start, end) ，其中 start 跟 end 兩個參數代表tree的值域範圍，而當取 i 為 root 時，左子樹群為 bst(start, i-1)，右子樹群為 bst(i+1, end)，base case 條件為 start > end，並回傳 NULL。

Python3：

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def printInOrder(root):
    if not root:
        print("None")
        return
    if root.left:
        printInOrder(root.left)
    print(root.val, end=" ")
    if root.right:
        printInOrder(root.right)

class Solution:
    def generateTrees(self, n: int) -> list[TreeNode]:
        def bst(start, end):
            if start > end:
                return [None]
            trees = []
            for i in range(start, end+1):
                leftTrees = bst(start, i-1)
                rightTrees = bst(i+1, end)
                for left in leftTrees:
                    for right in rightTrees:
                        trees.append(TreeNode(i, left, right))
            return trees
        return bst(1, n)

if __name__ == '__main__':
    n = 4

    ans = Solution().generateTrees(n)
    for t in ans:
        printInOrder(t)
        print()

C：

#include <stdio.h>
#include <stdlib.h>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* insertLevelOrder(int *arr, int arrSize, int i) {
    struct TreeNode *root = NULL;
    if (i < arrSize) {
        root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        root->val = arr[i];
        root->left = insertLevelOrder(arr, arrSize, 2 * i + 1);
        root->right = insertLevelOrder(arr, arrSize, 2 * i + 2);
    }
    return root;
}

void printInOrder(struct TreeNode* root) {
    if (root == NULL) {
        printf("None");
        return;
    }
    if (root->left != NULL)
        printInOrder(root->left);
    printf("%d ", root->val);
    if (root->right != NULL)
        printInOrder(root->right);
}

struct TreeNode** bst(int start, int end, int* returnSize) {
    if (start > end) {
        *returnSize = 1;
        struct TreeNode **trees = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
        trees[0] = NULL;
        return trees;
    }
    *returnSize = 0;
    struct TreeNode **trees = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
    int idx = 0;
    for (int i = start; i <= end; i++) {
        struct TreeNode **leftTrees, **rightTrees;
        int leftSize, rightSize;
        leftTrees = bst(start, i-1, &leftSize);
        rightTrees = bst(i+1, end, &rightSize);
        *returnSize += leftSize * rightSize;
        trees = realloc(trees, sizeof(struct TreeNode*) * (*returnSize));
        for (int j = 0; j < leftSize; j++) {
            for (int k = 0; k < rightSize; k++) {
                struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
                root->val = i;
                root->left = leftTrees[j];
                root->right = rightTrees[k];
                trees[idx++] = root;
            }
        }
    }
    return trees;
}

struct TreeNode** generateTrees(int n, int* returnSize) {
    return bst(1, n, returnSize);
}

int main() {
    int n = 3;
    int returnSize;
    
    struct TreeNode** ans = generateTrees(n, &returnSize);
    printf("returnSize: %d\n", returnSize);
    for (int i = 0; i < returnSize; i++) {
        printInOrder(ans[i]);
        printf("\n");
    }
    return 0;
}

###### tags: `leetcode` `binary tree` `recursion`