Unique Binary Search Trees ii


算法:二叉搜索树

url:https://leetcode-cn.com/problems/unique-binary-search-trees-ii/

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
给定一个整数 n,生成所有由 1 ... n 为节点所组成的二叉搜索树。
示例:

输入: 3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树:

1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

分析

首先来计数需要构建的二叉树数量。可能的二叉搜素数数量是一个 卡特兰数。

我们跟随上文的逻辑,只是这次是构建具体的树,而不是计数。

算法

我们从序列 1 ..n 中取出数字 i,作为当前树的树根。于是,剩余 i - 1 个元素可用于左子树,n - i 个元素用于右子树。
如 前文所述,这样会产生 G(i - 1) 种左子树 和 G(n - i) 种右子树,其中 G 是卡特兰数。

image.png

现在,我们对序列 1 … i - 1 重复上述过程,以构建所有的左子树;然后对 i + 1 … n 重复,以构建所有的右子树。

这样,我们就有了树根 i 和可能的左子树、右子树的列表。

最后一步,对两个列表循环,将左子树和右子树连接在根上。

Java解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public List<TreeNode> generateTrees(int n) {
if (n <= 0) {
return new LinkedList<TreeNode>();
}
return listTrees(1, n);
}

public LinkedList<TreeNode> listTrees(int start, int end) {
LinkedList<TreeNode> rootList = new LinkedList<TreeNode>();
if(start > end) {
rootList.add(null);
return rootList;
}
for(int i=start; i<=end; ++i) {
LinkedList<TreeNode> leftList = listTrees(start, i-1);
LinkedList<TreeNode> rightList = listTrees(i+1, end);
for(TreeNode left : leftList) {
for(TreeNode right : rightList) {
TreeNode cur = new TreeNode(i);
cur.left = left;
cur.right = right;
rootList.add(cur);
}
}
}
return rootList;
}

}

Python解法