UniqueBinarySearchTreesII [source code]
public class UniqueBinarySearchTreesII {
static
/******************************************************************************/
class Solution {
public List<TreeNode> generateTrees(int n) {
Map<Integer, List<TreeNode>> map = new HashMap<> ();
List<TreeNode> base_ls = new ArrayList<> ();
if (n == 0)
return base_ls;
base_ls.add (new TreeNode (1));
if (n == 1)
return base_ls;
map.put (1, base_ls);
for (int i = 2; i <= n; i++) {
List<TreeNode> size_ls = new ArrayList<> ();
for (int j = 1; j <= i; j++) {
int left_size = j - 1 - 1 + 1, right_size = i - (j + 1) + 1;
List<TreeNode> left_ls = map.get (left_size), right_ls = map.get (right_size);
List<TreeNode> new_left_ls = new ArrayList<> (), new_right_ls = new ArrayList<> ();
if (left_ls != null) {
for (TreeNode node : left_ls)
new_left_ls.add (copyTreeNode (node, 0));
} else new_left_ls.add (new TreeNode (0));
if (right_ls != null) {
for (TreeNode node : right_ls)
new_right_ls.add (copyTreeNode (node, j));
} else new_right_ls.add (new TreeNode (0));
for (TreeNode left_node : new_left_ls) {
for (TreeNode right_node : new_right_ls) {
TreeNode cur = new TreeNode (j);
cur.left = left_node.val == 0 ? null : left_node;
cur.right = right_node.val == 0 ? null : right_node;
size_ls.add (cur);
}
}
}
map.put (i, size_ls);
}
return map.get (n);
}
TreeNode copyTreeNode (TreeNode node, int offset) {
if (node == null)
return null;
TreeNode res = new TreeNode (node.val + offset);
res.left = copyTreeNode (node.left, offset);
res.right = copyTreeNode (node.right, offset);
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
UniqueBinarySearchTreesII.Solution tester = new UniqueBinarySearchTreesII.Solution();
int[] inputs = {
2,
3,
};
int k = 1;
for (int i = 0; i < inputs.length / k; i++) {
int n = inputs[k * i];
System.out.println (Printer.separator ());
tester.generateTrees (n);
}
}
}
很难吗? 好像跟第一题是不是差不多?
真的吗? 你别骗我; 仔细想了一下, 这个问题的一个难点是DP好像不是很好实现; 你TreeNode怎么实现深复制? 如果不能深复制, 就不能表格里面存放多个copy;
比较naive的想法就是自己实现一个copy constructor, 但是后来发现这个真的太麻烦了, 光是这个copy本身就很麻烦;
然后想到一个问题, 你真的需要copy吗? 当你走到一个size==i的时候, 所有更小的size全都已经计算了, 这个时候你需要做的, 其实就是让当前的root j,直接左右指向向下的小的subtree就行了; 最后数字可能有问题, 但是没关系, 最后单独给结果的tree一个InOrder traversal, 修改数字行不行? 我感觉是行的, 最关键的是structure本身要对; 不对, 好像不行, 比如size6的, 需要找size1和size4, 但是size4又需要size1和size2, 这样size1实际上在一个tree里面被共享了;
想到这里, 其实发现这个问题有点像CKY啊;
不管了, 直接用copy做一个算了;
写起来其实没有想想的那么复杂, 无论是设计还是实现; 最后一个难点是debug, 只好给TreeNode加了一个serialize函数, 最后才方便的debug出来了; 速度是5ms (8%), 没想到居然AC了, 虽然不是最优解但是是波动内的第一梯队, 看来这个题目考察的其实就是一个基本功操作, 对于指针和深复制这些东西的理解, 也就是考察你写代码的基本功, 基本思想其实是跟第一题一样的; 这么想下来, 搞不好这个第二题其实就是第一题的一个Follow-Up而已;
没有editorial;
I start by noting that 1…n is the in-order traversal for any BST with nodes 1 to n. So if I pick i-th node as my root, the left subtree will contain elements 1 to (i-1), and the right subtree will contain elements (i+1) to n. I use recursive calls to get back all possible trees for left and right subtrees and combine them in all possible ways with the root.
public class Solution {
public List<TreeNode> generateTrees(int n) {
return genTrees(1,n);
}
public List<TreeNode> genTrees (int start, int end)
{
List<TreeNode> list = new ArrayList<TreeNode>();
if(start>end)
{
list.add(null);
return list;
}
if(start == end){
list.add(new TreeNode(start));
return list;
}
List<TreeNode> left,right;
for(int i=start;i<=end;i++)
{
left = genTrees(start, i-1);
right = genTrees(i+1,end);
for(TreeNode lnode: left)
{
for(TreeNode rnode: right)
{
TreeNode root = new TreeNode(i);
root.left = lnode;
root.right = rnode;
list.add(root);
}
}
}
return list;
}
}
这个就是简单的recursion做法, 连memo都没有的;
Could be slightly simpler :)
public List<TreeNode> generateTrees(int n) {
return genTreeList(1,n);
}
private List<TreeNode> genTreeList (int start, int end) {
List<TreeNode> list = new ArrayList<TreeNode>();
if (start > end) {
list.add(null);
}
for(int idx = start; idx <= end; idx++) {
List<TreeNode> leftList = genTreeList(start, idx - 1);
List<TreeNode> rightList = genTreeList(idx + 1, end);
for (TreeNode left : leftList) {
for(TreeNode right: rightList) {
TreeNode root = new TreeNode(idx);
root.left = left;
root.right = right;
list.add(root);
}
}
}
return list;
}
不过用首尾坐标来divide确实还是很方便的一个想法;
Using DP causes two problems:
- It consumes lots of space, so possible running out of heap space for large n
- Using DP means you are reusing Subtree[start, end] solution. Which means if two unique BST both contains Subtree[3, 5], you are using the same saved subtree in two different BST. It is not a completely deep copy.
这个确实是真的, 我感觉DP真的是要占用相当大的空间; 其实最后就是一个time space Trade-Off了;
cached version
public List<TreeNode> generateTrees(int n) {
if (0 == n) return new ArrayList<>();
return generateTrees(1, n);
}
private Map<String, List<TreeNode>> trees = new HashMap<>();
public List<TreeNode> generateTrees(int lo, int hi) {
// cache
String key = "" + lo + "." + hi;
if (trees.containsKey(key)) return trees.get(key);
List<TreeNode> res = new ArrayList<>();
if (lo == hi) {
res.add(new TreeNode(lo));
return res;
}
else if (lo > hi) {
res.add(null);
return res;
}
for (int x = lo; x <= hi; ++x) {
// tree that with x as root
List<TreeNode> leftList = generateTrees(lo, x - 1);
List<TreeNode> rightList = generateTrees(x + 1, hi);
for (TreeNode left : leftList) {
for (TreeNode right : rightList) {
TreeNode root = new TreeNode(x);
root.left = left;
root.right = right;
res.add(root);
}
}
}
trees.put(key, res);
return res;
}
这个就是硬cache的做法, 直接自己做的key, 而不是想到用size做key然后copy的时候改value; 实际上, 他这个cache效率是不如我的, 他这个做法里面1 2和5 6用的是不同的entry, 但是实际上他们都是size=2, 所以用同一个entry就行了; 他这样的memo因为根本不考虑hit率, 实际上我感觉有用吗? 根本没用吧? 比如1..3 4 5..8, 你1..3和5..8向下recurse的时候, 根本不会hit任何其他之前已经计算过的key;
果然, 是没有用的, 我改了这个:
if (trees.containsKey(key)) {
System.out.println ("cache hit");
return trees.get(key);
}
结果根本没有hit过; 不对, 3的时候虽然没有hit, 但是9的时候hit了很多; 奇怪了; 好像还是有可能的, [1,3] 4 [[5,6] 7 [8, 10]]和[[1,3] 4 [5,6]] 7 [8, 10]之间还是有overlap的;
总体来说这个memo的效率还是很低; 但是避免了深复制的难题;
https://leetcode.com/problems/unique-binary-search-trees-ii/discuss/31493/Java-Solution-with-DP
Here is my java solution with DP:
public static List<TreeNode> generateTrees(int n) {
List<TreeNode>[] result = new List[n + 1];
result[0] = new ArrayList<TreeNode>();
if (n == 0) {
return result[0];
}
result[0].add(null);
for (int len = 1; len <= n; len++) {
result[len] = new ArrayList<TreeNode>();
for (int j = 0; j < len; j++) {
for (TreeNode nodeL : result[j]) {
for (TreeNode nodeR : result[len - j - 1]) {
TreeNode node = new TreeNode(j + 1);
node.left = nodeL;
node.right = clone(nodeR, j + 1);
result[len].add(node);
}
}
}
}
return result[n];
}
private static TreeNode clone(TreeNode n, int offset) {
if (n == null) {
return null;
}
TreeNode node = new TreeNode(n.val + offset);
node.left = clone(n.left, offset);
node.right = clone(n.right, offset);
return node;
}
result[i] stores the result until length i. For the result for length i+1, select the root node j from 0 to i, combine the result from left side and right side. Note for the right side we have to clone the nodes as the value will be offsetted by j.
没想到array of list是可以用的? 我怎么记得是不能用的?
他处理empty list的方式也和我不一样: result[0].add(null);. 这个操作居然是可以的;
java> List<Integer> ls = new ArrayList<> ()
java.util.List<java.lang.Integer> ls = []
java> ls.add (null)
java.lang.Boolean res1 = true
java> ls.size ()
java.lang.Integer res2 = 1
真是活久见了;
他这个算法一个比我的算法重大的优化在于, 你看他对于每一个j(他这里是j+1作为root), 他右半边是clone的, 但是左半边是不clone的! 这个很聪明:
This is because for the left nodes, they always start from 1, which have the same values with those in dp[]; While the right nodes, starting at j+1, so they need offset = j+1;
想一想还真的是这么回事, 所有1..j样式的tree, 永远都不会被修改, 所以没有必要被clone; 虽然最后可能比如一个1..4的tree, 头上会有好几个parent, 但是这个无所谓, 最后我们返回的结果是不会出问题的;
顺手又重新观察了一下我的代码, 我很多地方可以修改, 比如我的两个new_ls, 实际上完全是为了handle Empty而出现的, 你看他的方法里面, 就没有这个部分; 这两个new list按理来说应该是可以给删掉的;
This problem is a variant of the problem of Unique Binary Search Trees.
I provided a solution along with explanation for the above problem, in the question “DP solution in 6 lines with explanation”
It is intuitive to solve this problem by following the same algorithm. Here is the code in a divide-and-conquer style.
public List<TreeNode> generateTrees(int n) {
return generateSubtrees(1, n);
}
private List<TreeNode> generateSubtrees(int s, int e) {
List<TreeNode> res = new LinkedList<TreeNode>();
if (s > e) {
res.add(null); // empty tree
return res;
}
for (int i = s; i <= e; ++i) {
List<TreeNode> leftSubtrees = generateSubtrees(s, i - 1);
List<TreeNode> rightSubtrees = generateSubtrees(i + 1, e);
for (TreeNode left : leftSubtrees) {
for (TreeNode right : rightSubtrees) {
TreeNode root = new TreeNode(i);
root.left = left;
root.right = right;
res.add(root);
}
}
}
return res;
}
这个就是一个简单的recursion; 注意他每一个iteration上来的res就是new出来的, 因为这里要避免通过指针传递进行的return: shared object;
https://oj.leetcode.com/discuss/24282/dp-solution-in-6-lines-with-explanation-f-i-g-i-1-g-n-i
Then @6219221 reminded me it is unnecessary to create the BSTs with all brand new nodes.
Assume you have a list of all BSTs with values from 1 to n-1, every possible way to insert value n only involves changing the right tree (root inclusive) because n is always greater than root.val and the left subtree structure is fixed. So all we gotta do is to create a new copy of the right part of the tree and point the new root.left to the original left subtree. This way we reuse the left tree, which saves time and space.How to insert Node n into the right subtree?
Given any BST on the n - 1 level, it will be only valid to put n on the root.right, root.right.right or root.right…right locations and then move the right subtree of n.right…right to become the left child of n, in order to keep n on the right-most position as the greatest value in the tree.Here is my implementation. Note that I do the dp from [n] back to [n to 1]. Therefore all the right subtree structures are fixed and new values are inserted into the left side, opposite to making BSTs from 1 to [1 to n].
public List<TreeNode> generateTrees(int n) {
List<TreeNode> res = new ArrayList<>();
res.add(null);
for(; n > 0; n--) {
List<TreeNode> next = new ArrayList<>();
for(TreeNode node: res) {
//the special case when Node(n) is root of new tree
TreeNode root = new TreeNode(n);
root.right = node;
next.add(root);
//while loop inserts new value to every possible position into the left tree side
while(node != null) {
TreeNode cRoot = new TreeNode(root.right.val);
//clone left subtree
cRoot.left = copyTree(root.right.left);
//reusing - point new root.right to the original right subtree
cRoot.right = root.right.right;
//curr is the cutoff node whose right child will be replaced by the new n
TreeNode curr = getValNode(cRoot, node.val);
//place n as curr's right child, make curr's original right child as the left child of n.
TreeNode tmp = curr.left;
curr.left = new TreeNode(n);
curr.left.right = tmp;
next.add(cRoot);
node = node.left;
}
}
res = next;
}
return res;
}
private TreeNode getValNode(TreeNode n, int val) { //find the cutoff node in the new tree
while(n != null) {
if(n.val == val) break;
n = n.left;
}
return n;
}
private TreeNode copyTree(TreeNode root) { //clone the right subtree
if(root == null) return null;
TreeNode cRoot = new TreeNode(root.val);
cRoot.left = copyTree(root.left);
cRoot.right = copyTree(root.right);
return cRoot;
}
这个其实就是一个reduce的思路, 直接就是每一个新来的好像找专门的插入位置?
配合他的解说大概能理解一点; 他每次都是从n(新加入的数字)在最上面的root开始, 然后将n向下移动: 这个实现是向左边的下面;
大概的思想还是能理解的, 就是这个算法最后代码实现起来真的不是一般人能够驾驭的, 逻辑要相当的清楚; 光是3的case, 我就已经画了半天了, 而实际上这个3的case并不够typical, 感觉不少逻辑其实还没有涵盖到;
他这个算法的优势就是space占用要小的多; 但是实际上也不是彻底的降低, 因为实际上还是要依赖大量的copy的; 然后他这个get, 有说法啊, 一直不停的要走一个额外的lookup; 虽然说BST的lookup是logN的, 但是这个其实还是一个不利因素;
有得有失的一个实现方式, 因为代码复杂度比较高, 我个人还是不太支持这个说法, 不过OP水平还是足见一斑的;
submission最优解: 3(72):
class Solution {
public List<TreeNode> generateTrees(int n) {
if(n < 1)
return new ArrayList<>();
List<TreeNode>[][] dp = new List[n+2][n+2];
return helper(1, n, dp);
}
public List<TreeNode> helper(int start, int end, List[][] dp){
if(dp[start][end] != null)
return dp[start][end];
List<TreeNode> list = new ArrayList<>();
if(start > end){
list.add(null);
}
else if(start==end){
list.add(new TreeNode(start));
}
else{
for(int i = start; i <= end; i++){
List<TreeNode> left = helper(start, i-1, dp);
List<TreeNode> right = helper(i+1, end, dp);
for(TreeNode l : left){
for(TreeNode r : right){
TreeNode node = new TreeNode(i);
node.left = l;
node.right = r;
list.add(node);
}
}
}
}
dp[start][end] = list;
return list;
}
}
就是用数组完成的一个naive的memo; 我还是有点吃惊array of lists居然成立;
Problem Description
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
Difficulty:Medium
Total Accepted:97.1K
Total Submissions:302.5K
Contributor:LeetCode
Related Topics
dynamic programmingtree
Similar Questions
Unique Binary Search TreesDifferent Ways to Add Parentheses