LeetCode 95 - Unique Binary Search Trees II

作者 QIFAN 日期 2017-01-07
LeetCode 95 - Unique Binary Search Trees II

原题链接: 95. Unique Binary Search Trees II


题干

96. Unique Binary Search Trees 的扩展版。

给定一个数字 n ,返回可由 1 ~ n 构成的所有二叉搜索树。

思路

还是插入顺序的问题。但是为什么结果不是 $n!$ 颗树呢?
假设 i , j 先后插入树。如果完全按照顺序来,那 j 必定是 i 的孩子。而在向下遍历找插入点时,如果 i 在左子树,而 j 要去右子树,那 j 必然就不能成为 i 的孩子,所以就会造成一些重复。

这个条件应该怎么判断?
假设当前节点是 curr ,那 i 和 j 不在 curr 的同边的情况是 i < curr < j 或 j < curr < i 。
概括一下就是 (i - curr) * (j - curr) < 0

思路就是这样:

设当前要插入 i 。
for 树 in 上一步生成的树:
for k in (1, i - 1):
判断能否在 k 后插入 i
if 能插入:
克隆原树,插入 i
加入 list
加入 i 作为根节点的树

这个时间空间就不算了。。

代码:

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<TreeNode> generateTrees(int n) {
List<TreeNode> res = new ArrayList<>();
if (n == 0) {
return res;
}
TreeNode tree = new TreeNode(1);
res.add(tree);
for (int i = 2; i <= n; i++) {
// 获取上一步生成的树的数量
int lastSize = res.size();
for(int j = 0; j < lastSize; j++) {
// 由于每次在后面加,然后会移除第一个,所以每次第一个都是新的
TreeNode currTree = res.get(0);
TreeNode newTree = null;
for (int k = 1; k < i; k++) {
// 如果上一轮生成了新树,那就再深复制一个
if (newTree == null) {
newTree = clone(currTree);
}
// 如果可以插入 i 作为 k 的子节点
if (insertAfter(i, k, newTree)) {
res.add(newTree);
newTree = null;
}
}
// 以 i 作为根的树
newTree = new TreeNode(i);
newTree.left = currTree;
res.add(newTree);
res.remove(0);
}
}
return res;
}
public boolean insertAfter(int item, int key, TreeNode tree) {
TreeNode curr = tree;
while (curr.val != key) {
if ((item - curr.val) * (key - curr.val) < 0) {
return false;
}
if (key < curr.val) {
curr = curr.left;
} else {
curr = curr.right;
}
}
TreeNode tmp = new TreeNode(item);
if (curr.right != null) {
tmp.left = curr.right;
}
curr.right = tmp;
return true;
}
public TreeNode clone(TreeNode tree) {
TreeNode copy = new TreeNode(tree.val);
clone(tree, copy);
return copy;
}
public void clone(TreeNode tree, TreeNode copy) {
if (tree == null) {
return;
}
if (tree.left != null) {
copy.left = new TreeNode(tree.left.val);
clone(tree.left, copy.left);
}
if (tree.right != null) {
copy.right = new TreeNode(tree.right.val);
clone(tree.right, copy.right);
}
}
}