95.不同的二叉搜索树Ⅱ
Snake8859 二叉树
# 题目描述
给你一个整数 n
,请你生成并返回所有由 n
个节点组成且节点值从 1
到 n
互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
示例 1:
输入:n = 3
输出:[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
1
2
2
示例 2:
输入:n = 1
输出:[[1]]
1
2
2
# 外地解法-二叉搜索树的构造
这道题是思路是:
1、穷举root
节点的所有可能。
2、递归构造出左右子树的所有合法 BST。
3、给root
节点穷举所有左右子树的组合。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<TreeNode> generateTrees(int n) {
if (n == 0) return new LinkedList<>();
// 构造闭区间 [1, n] 组成的 BST
return build(1, n);
}
public List<TreeNode> build(int lo, int hi){
List<TreeNode> res = new LinkedList<>();
// base case
if(lo > hi){
res.add(null);
return res;
}
// 穷举root节点的所有可能
for(int i = lo; i <= hi; i++){
// 递归构造左右子树
List<TreeNode> leftTree = build(lo, i - 1);
List<TreeNode> rightTree = build(i + 1, hi);
// 给 root 节点穷举所有左右子树的组合。
for (TreeNode left : leftTree) {
for (TreeNode right : rightTree) {
// i 作为根节点 root 的值
TreeNode root = new TreeNode(i);
root.left = left;
root.right = right;
res.add(root);
}
}
}
return res;
}
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51