# 不同的二叉搜索树 II

<div class="notranslate">
    <p>给你一个整数 <code>n</code> ，请你生成并返回所有由 <code>n</code> 个节点组成且节点值从 <code>1</code> 到 <code>n</code> 互不相同的不同
        <strong>二叉搜索树</strong><em> </em>。可以按 <strong>任意顺序</strong> 返回答案。
    </p>

    <p>&nbsp;</p>

    <div class="original__bRMd">
        <div>
            <p><strong>示例 1：</strong></p>
            <img style="width: 600px; height: 148px;"
                src="https://assets.leetcode.com/uploads/2021/01/18/uniquebstn3.jpg" alt="">
            <pre><strong>输入：</strong>n = 3
<strong>输出：</strong>[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
    </pre>

            <p><strong>示例 2：</strong></p>

            <pre><strong>输入：</strong>n = 1
<strong>输出：</strong>[[1]]
    </pre>

            <p>&nbsp;</p>

            <p><strong>提示：</strong></p>

            <ul>
                <li><code>1 &lt;= n &lt;= 8</code></li>
            </ul>
        </div>
    </div>
</div>

以下程序实现了这一功能，请你填补空白处内容：

```cpp
#include <stdio.h>
#include <stdlib.h>
struct TreeNode
{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
};
static struct TreeNode *dfs(int low, int high, int *count)
{
	int i, j, k;
	if (low > high)
	{
		*count = 0;
		return NULL;
	}
	else if (low == high)
	{
		struct TreeNode *node = malloc(sizeof(*node));
		node->val = low;
		node->left = NULL;
		node->right = NULL;
		*count = 1;
		return node;
	}
	else
	{
		*count = 0;
		int capacity = 5;
		struct TreeNode *roots = malloc(capacity * sizeof(struct TreeNode));
		for (i = low; i <= high; i++)
		{
			int left_cnt, right_cnt;
			________________________________;
			if (left_cnt == 0)
				left_cnt = 1;
			if (right_cnt == 0)
				right_cnt = 1;
			if (*count + (left_cnt * right_cnt) >= capacity)
			{
				capacity *= 2;
				capacity += left_cnt * right_cnt;
				roots = realloc(roots, capacity * sizeof(struct TreeNode));
			}
			for (j = 0; j < left_cnt; j++)
			{
				for (k = 0; k < right_cnt; k++)
				{
					roots[*count].val = i;
					roots[*count].left = left_subs == NULL ? NULL : &left_subs[j];
					roots[*count].right = right_subs == NULL ? NULL : &right_subs[k];
					(*count)++;
				}
			}
		}
		return roots;
	}
}
static struct TreeNode **generateTrees(int n, int *returnSize)
{
	int i, count = 0;
	struct TreeNode *roots = dfs(1, n, &count);
	struct TreeNode **results = malloc(count * sizeof(struct TreeNode *));
	for (i = 0; i < count; i++)
	{
		results[i] = &roots[i];
	}
	*returnSize = count;
	return results;
}
static void dump(struct TreeNode *node)
{
	printf("%d ", node->val);
	if (node->left != NULL)
	{
		dump(node->left);
	}
	else
	{
		printf("# ");
	}
	if (node->right != NULL)
	{
		dump(node->right);
	}
	else
	{
		printf("# ");
	}
}
int main(int argc, char **argv)
{
	if (argc != 2)
	{
		fprintf(stderr, "Usage: ./test n\n");
		exit(-1);
	}
	int i, count = 0;
	struct TreeNode **results = generateTrees(atoi(argv[1]), &count);
	for (i = 0; i < count; i++)
	{
		dump(results[i]);
		printf("\n");
	}
	return 0;
}
```

## template

```cpp
#include <stdio.h>
#include <stdlib.h>
struct TreeNode
{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
};
static struct TreeNode *dfs(int low, int high, int *count)
{
	int i, j, k;
	if (low > high)
	{
		*count = 0;
		return NULL;
	}
	else if (low == high)
	{
		struct TreeNode *node = malloc(sizeof(*node));
		node->val = low;
		node->left = NULL;
		node->right = NULL;
		*count = 1;
		return node;
	}
	else
	{
		*count = 0;
		int capacity = 5;
		struct TreeNode *roots = malloc(capacity * sizeof(struct TreeNode));
		for (i = low; i <= high; i++)
		{
			int left_cnt, right_cnt;
			struct TreeNode *left_subs = dfs(low, i - 1, &left_cnt);
			struct TreeNode *right_subs = dfs(i + 1, high, &right_cnt);
			if (left_cnt == 0)
				left_cnt = 1;
			if (right_cnt == 0)
				right_cnt = 1;
			if (*count + (left_cnt * right_cnt) >= capacity)
			{
				capacity *= 2;
				capacity += left_cnt * right_cnt;
				roots = realloc(roots, capacity * sizeof(struct TreeNode));
			}
			for (j = 0; j < left_cnt; j++)
			{
				for (k = 0; k < right_cnt; k++)
				{
					roots[*count].val = i;
					roots[*count].left = left_subs == NULL ? NULL : &left_subs[j];
					roots[*count].right = right_subs == NULL ? NULL : &right_subs[k];
					(*count)++;
				}
			}
		}
		return roots;
	}
}
static struct TreeNode **generateTrees(int n, int *returnSize)
{
	int i, count = 0;
	struct TreeNode *roots = dfs(1, n, &count);
	struct TreeNode **results = malloc(count * sizeof(struct TreeNode *));
	for (i = 0; i < count; i++)
	{
		results[i] = &roots[i];
	}
	*returnSize = count;
	return results;
}
static void dump(struct TreeNode *node)
{
	printf("%d ", node->val);
	if (node->left != NULL)
	{
		dump(node->left);
	}
	else
	{
		printf("# ");
	}
	if (node->right != NULL)
	{
		dump(node->right);
	}
	else
	{
		printf("# ");
	}
}
int main(int argc, char **argv)
{
	if (argc != 2)
	{
		fprintf(stderr, "Usage: ./test n\n");
		exit(-1);
	}
	int i, count = 0;
	struct TreeNode **results = generateTrees(atoi(argv[1]), &count);
	for (i = 0; i < count; i++)
	{
		dump(results[i]);
		printf("\n");
	}
	return 0;
}
```

## 答案

```cpp
struct TreeNode *left_subs = dfs(low, i - 1, &left_cnt);
struct TreeNode *right_subs = dfs(i + 1, high, &right_cnt);
```

## 选项

### A

```cpp
struct TreeNode *left_subs = dfs(low, i + 1, &left_cnt);
struct TreeNode *right_subs = dfs(i + 1, high, &right_cnt);
```

### B

```cpp
struct TreeNode *left_subs = dfs(low, i - 1, &left_cnt);
struct TreeNode *right_subs = dfs(i - 1, high, &right_cnt);
```

### C

```cpp
struct TreeNode *left_subs = dfs(high, i - 1, &left_cnt);
struct TreeNode *right_subs = dfs(i + 1, low, &right_cnt);
```