共计 1522 个字符，预计需要花费 4 分钟才能阅读完成。
Leetcode 95
不同的二叉搜索树 II
输入: 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
Leetcode 86
不同的二叉搜索树
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
题解
搜索二叉树 (BST) 的定义
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。
给点一个数，去构造 BST.[1, 2, 3]可以把这个数列做左子树和右子树的划分:[1] [2, 3][1, 2] [3]
[1, 2] [2, 3] 又可以做左子树和右子树的划分. 这是一个递归的过程. 把递归的结果构造起来, 即可成为答案.
/**
* Definition for a binary tree node.
* 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 ArrayList<>();
return generateBST(1, n);
}
private List<TreeNode> generateBST(int left, int right) {
List<TreeNode> res = new LinkedList<>();
if (left > right) {
// 划分不到的时候, 这时候填 null.
res.add(null);
return res;
}
for (int i = left; i <= right; i++) {
List<TreeNode> leftTrees = generateBST(left, i – 1);
List<TreeNode> rightTrees = generateBST(i + 1, right);
for (TreeNode leftTree : leftTrees) {
for (TreeNode rightTree : rightTrees) {
// 注意, 每个循环都要构造新的节点, 不能在 for 循环外面生成.
TreeNode root = new TreeNode(i);
root.left = leftTree;
root.right = rightTree;
res.add(root);
}
}
}
return res;
}
}
如果只需要数目, 不需要生成具体的 BST 的话, 只要能求出左子树有几种构造, 右子树有几种构造, 就可以最终确定.
而确定左子树和右子树的问题的时候, 又可以划分为子问题.eg: 求 [1,2,3,4] 依赖于:[1,2,3] [2,3,4]又依赖于:[1,2] [2,3] [3,4]的构造有几种.
class Solution {
public int numTrees(int n) {
int[] res = new int[n + 2];
res[0] = 1;
res[1] = 1;
// 没有左子树和右子树
res[2] = 2;
for (int i = 3; i <= n; i++) {
// 从 3 求到 n
for (int j = 1; j <= i; j++) {
// 求解过程中, 需要依赖于之前的解, 状态转移方程为每一种划分的左子树和右子树的构造方法乘积.
res[i] += res[j – 1] * res[i – j];
}
}
return res[n];
}
}
