Massive Algorithms: LeetCode 95

Related: LeetCode 96 - Unique Binary Search Trees I
https://leetcode.com/problems/unique-binary-search-trees-ii/

Given 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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Related LeetCode 96 - Unique Binary Search Trees
X. DP

https://leetcode.com/problems/Unique-Binary-Search-Trees-II/discuss/31493/Java-Solution-with-DP

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.

the reason we have to "clone" here is because nodeL and nodeR can be the same TreeNode, and if you link the same node to a root as left and right children, may lead wrong tree construction/ conflict.

Why do we need the clone method, and Why we apply it on the right subtree only!?

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;
F(i, j) = G(j-1) * G(i-j)
G(n) = F(1, n) + F(2, n) + ... + F(n, n);
G(n) = G(0, n-1) + G(1, n-2) + .. + G(n-1) * G(0)

Your code is better than mine, but it's not easy to understand why not to clone left, there're some node share,but it doesn't matter,because they are all left node.And it took me some time to understand.

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

X. DFS

https://discuss.leetcode.com/topic/8410/divide-and-conquer-f-i-g-i-1-g-n-i

I just add an HashMap as the cache, but I'm wondering why the algorithm costs more time.

I would say the time complexity would be exponential. Since it can be found out from his code that T(n) = 2*(T(n-1) + T(n-2) + ... + T(1) + T(0)), T(n) should equal to $O(2^n)$

T(n)=T(0)T(n-1)+T(1)T(n-2)+...+T(n-1)T(0)

Catalan Number T(n) = C(n,2n)/(n+1), so it's about O(n^(n-1))

https://zxi.mytechroad.com/blog/uncategorized/leetcode-95-unique-binary-search-trees-ii/

for i in 1..n: pick i as root,
left subtrees can be generated in the same way for n_l = 1 … i – 1,
right subtrees can be generated in the same way for n_r = i + 1, …, n
def gen(s, e):
return [tree(i, l, r) for l in gen(s, i – 1) for r in gen(i + 1, e) for i in range(s, e+1)

# of trees:

n = 0: 1
n = 1: 1
n = 2: 2
n = 3: 5
n = 4: 14
n = 5: 42
n = 6: 132
…
Trees(n) = Trees(0)*Trees(n-1) + Trees(1)*Trees(n-2) + … + Tress(n-1)*Trees(0)

Time complexity: O(3^n)

Space complexity: O(3^n)

  public List<TreeNode> generateTrees(int n) {

    if (n == 0) return new ArrayList<TreeNode>();

    return generateTrees(1, n);

}

  private List<TreeNode> generateTrees(int l, int r) {

    List<TreeNode> ans = new ArrayList<>();

    if (l > r) {      

      ans.add(null);

      return ans;

}

    for (int i = l; i <= r; ++i)

      for (TreeNode left : generateTrees(l, i - 1))

        for (TreeNode right: generateTrees(i + 1, r)) {

          TreeNode root = new TreeNode(i);

          root.left = left;

          root.right = right;

          ans.add(root);

}

    return ans;

}

http://n00tc0d3r.blogspot.com/2013/07/unique-binary-search-trees_6.html
Think it in a deductive way:

n=1, one unique BST.
n=2, pick one value, and the one remaining node can be built as one BST, i.e. Two BSTs.
... ...
n=k, pick one value i, and split the remaining values to two groups: [1 .. i-1] goes to left subtree and [i+1 .. n] goes to right subtree. Then the problem becomes to construct BSTs with left subtree from BST(1, i-1) and right subtree from BST(i+1, n), where BST(1, i-1) and BST(i+1, n) has been computed in previous iterations.

It is easy to get to a recursive solution:

Given a range [l .. r], if l > r, return a list containing an empty tree.
Otherwise, for each value k between l and r, inclusively

recursively compute BSTs in range [l .. k-1] and range [k+1 .. r]
construct BSTs with root of k, left subtree from BST(1, i-1) and right subtree from BST(i+1, n).

This algorithm runs in exponential time (much greater then the actual total count of unique BSTs) since we recompute BSTs in subrange [i .. j] repeatedly.

https://discuss.leetcode.com/topic/3079/a-simple-recursive-solution

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.

There is shared sub problem, but generate method is called every time. So no need to clone at all

X. DP

We probably could view the time complexity from another aspect.

Consider what this algorithm do. It generates possible BST for numbers from 1 to n. It first generate possible BST for [1], then for [1,2], ... then [1,2,...n]. And it traversed each of the results. Thus I would say the total time complexity is equal to the sum of the total number of unique binary trees for [1], [1,2], ... [1,2, ...n]. I don't really know how many unique BST for n numbers, but for unique Binary tree, the number is (2n)!/((n+1)!n!)

https://discuss.leetcode.com/topic/12559/java-dp-solution-and-brute-force-recursive-solution

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].

Hi, your solution is not a DP. So there will exist so many duplicate trees created during the recursion, which will waste too much time.

Oh yes. It took me a while to see what you are saying. Subtrees could be reused with the DP approach. Not only it saves time but also space is freed from creating extra nodes of the same value. Although having trees that share branches could be tricky to deal with in the real world, it is the best solution for an algorithm exercise indeed.

Your code is better than mine, but it's not easy to understand why not to clone left, there're some node share,but it doesn't matter,because they are all left node.And it took me some time to understand.there is my solution for more easy to understand.

    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;
    }

https://blog.csdn.net/Yaokai_AssultMaster/article/details/51898240

X. DP 2
https://discuss.leetcode.com/topic/3079/a-simple-recursive-solution/10

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.

Noticing the repeat computation in the above algorithm gives us a hint of DP: Can we store some intermediate results so as to reuse it rather than recomputing it?

The answer is yes and we can store BSTs of range [i .. i+k] and then for next range [i .. i+k+1] we can reuse previous results!

Create a table T containing lists of BSTs such that T[i, l] = a list of BSTs of range [i .. i+l].
Initialize the table with T[i, 0] which are all single node trees.
Increasing the size of range from 1 to n-1 and fill up the table.
For each range size l,

For each starting value i,

For each value k in [i, i+l], construct BSTs with root of k, left subtree from BSTs of [i, k-i-1] and right subtree from BSTs of [k+1, i+l-k-1].

Finally, T[0, n-1] gives us the result of all BSTs.

Exponential time: since we recompute BSTs in subrange [i .. j] repeatedly.

This algorithm sacrifice space for time. Since each subtree is only computed and stored once, the time and space complexities are equal to the total number of unique BSTs, which is the Catalan number as proven in previous post.

There are other ways to build such a table. For example, build up a table of T such that T[i, j] = a list of BSTs of range [i .. j]. In that case, for each T[i, j] where i > j we need to put an empty tree there.

public ArrayList<TreeNode> generateTrees(int n) {  
   if (n < 1) {  
     ArrayList<TreeNode> trees = new ArrayList<TreeNode>();  
     trees.add(null);  
     return trees;  
   }  
   
   // T[i,l] contains a list of BSTs of [i .. i+l]  
   ArrayList<ArrayList<ArrayList<TreeNode>>> allNumTrees = new ArrayList<ArrayList<ArrayList<TreeNode>>>(n);  
   
   // init with single node trees  
   for (int i=1; i<=n; ++i) {  
     ArrayList<ArrayList<TreeNode>> numTrees = new ArrayList<ArrayList<TreeNode>>(n-i);  
     ArrayList<TreeNode> trees = new ArrayList<TreeNode>();  
     TreeNode root = new TreeNode(i);  
     trees.add(root);  
     numTrees.add(trees);  
     allNumTrees.add(numTrees);  
   }  
   
   // fill up the table  
   for (int l=1; l<n; ++l) { // levels  
     for (int i=0; i<n-l; ++i) { // starting number  
       ArrayList<ArrayList<TreeNode>> numTrees = allNumTrees.get(i);  
       ArrayList<TreeNode> trees = new ArrayList<TreeNode>();  
       for (int k=i; k<=i+l; ++k) { // root value  
         if (k == i) {  
           for (TreeNode right : allNumTrees.get(k+1).get(l-1)) {  
             TreeNode root = new TreeNode(k+1);  
             root.right = right;  
             trees.add(root);  
           }  
         } else if (k == i+l) {  
           for (TreeNode left : allNumTrees.get(i).get(l-1)) {  
             TreeNode root = new TreeNode(k+1);  
             root.left = left;  
             trees.add(root);  
           }  
         } else {  
           for (TreeNode left : allNumTrees.get(i).get(k-i-1)) {  
             for (TreeNode right : allNumTrees.get(k+1).get(i+l-k-1)) {  
               TreeNode root = new TreeNode(k+1);  
               root.left = left;  
               root.right = right;  
               trees.add(root);  
             }  
           }  
         }  
       }  
       numTrees.add(trees);  
     }  
   }  
   
   return allNumTrees.get(0).get(n-1);  
 }

https://blog.csdn.net/Yaokai_AssultMaster/article/details/51898240
根据cracking the coding interview中的优化理念，我们首先考虑优化BUD(Bottleneck, Unnecessary work, Duplicated work)。显然其中的Duplicated work已经在动态规划的缓存这一步被解决了。而Bottleneck又不是很明显，那么只能寻找Unnecessary work了。
根据BST的对称性（既：i+1到n结点构成的BST和从1到n-i结点构成的DST结构完全相同，只有结点数值的区别。）那么我们可以用这一点减少数组的一个维度，只用二位数组来缓存。既数组的第一个维度i代表从第1个结点到第i个结点，第二个维度存储从第1到第i个结点的所有BST。通过这种方法，我们解决了Unnecessary work。
之所以代码中只对右子树使用clone方法，是因为只有右子树中的结点的值需要被改变（原因如上）。而offset参数即是需要改变的大小。

X. https://blog.csdn.net/Yaokai_AssultMaster/article/details/51898240

以上方法是没有使用记忆的。根据之前的分析，在这个算法中使用记忆需要构造一个三维数组。其中前两位分别对应BST的开始结点和结束结点的信息，第三位保存这些结点构成的BST。如下所示：

List<List<List<TreeNode>>> BSTcache = new ArrayList<List<List<TreeNode>>>;

1

我们可以使用如下方法来进行初始化操作：

for (int i = 0; i < n; i++){

List<List<TreeNode>> yrow = new ArrayList<List<TreeNode>>(n);

BSTcache.add(yrow);

for(int j = 0; j < n; j++){

List<TreeNode> zrow = new ArrayList<TreeNode>();

BSTcache.get(i).add(zrow);

}

这样我们就创造了一个前两维为而第三维大小不定的三维动态数组。我们用BSTcache.get(i).get(j)即可取出从第i个结点开始到第j个结点结束的所有BST构成的ArrayList。

https://leetcode.com/problems/unique-binary-search-trees-ii/discuss/166620/Java-DP-store-both-left-and-right-part

Similar idea. But I construct and store both the left and right part. For example, n = 5, and for dp[3], I not only store all unique BST from{1,2,3}, but also {2,3,4}, {3,4,5}. So it can be reused as the right subtree for dp[4] and dp[5]. No need to clone all the right subtree.

For example: n = 5, so dp[3] is all unique BST with {{1,2,3}, {2,3,4}, {3,4,5}}
The reason to store {2,3,4}, {3,4,5} is we need to use it as right subtree in generate dp[4], dp[5]
So, in generating dp[4], we can let 1/2/3/4 be the root, and the left subtree and right subtree could be retrieved from dp.

    public List<TreeNode> generateTrees(int n) {
        if(n == 0) return new ArrayList<TreeNode>();
        List<List<TreeNode>>[] dp = new List[n + 1];
        dp[0] = new ArrayList<List<TreeNode>>();
        for(int j = 1; j <= n + 1; j++){
            List<TreeNode> temp = new ArrayList<>();
            temp.add(null);
            dp[0].add(temp);
        }        
        dp[1] = new ArrayList<List<TreeNode>>();
        for(int j = 1; j <= n; j++){
            List<TreeNode> temp = new ArrayList<>();
            TreeNode tempNode = new TreeNode(j);
            temp.add(tempNode);
            dp[1].add(temp);
        }        
        for(int i = 2; i < dp.length; i++){
            dp[i] = new ArrayList<List<TreeNode>>();
            generateTreesHelper(dp, i, n);
        }
        return dp[n].get(0);
    }
    
    public void generateTreesHelper(List<List<TreeNode>>[] dp, int n, int total){
        for(int i = 1; i <= total - n + 1; i++){ // for example, n = 4. we need to generate 1234, 2345, 3456
            List<TreeNode> l = new ArrayList<>();
            for(int j = i; j < n + i; j++){
                List<TreeNode> left = dp[j - i].get(i - 1);
                List<TreeNode> right = dp[n + i - j - 1].get(j);
                for(TreeNode leftNode : left){
                    for(TreeNode rightNode : right){
                        TreeNode root = new TreeNode(j);
                        root.left = leftNode;
                        root.right = rightNode;
                        l.add(root);
                    }
                }   
            }
            dp[n].add(l);
        }
    }

https://leetcode.com/discuss/10254/a-simple-recursive-solution http://www.programcreek.com/2014/05/leetcode-unique-binary-search-trees-ii-java/
https://leetcode.com/discuss/24305/divide-and-conquer-f-i-g-i-1-g-n-i

public List<TreeNode> generateTrees(int n) {
    return generateTrees(1, n);
}
public List<TreeNode> generateTrees(int start, int end) {
    List<TreeNode> list = new LinkedList<>();
 
    if (start > end) {
        list.add(null);
        return list;
    }
 
    for (int i = start; i <= end; i++) {
        List<TreeNode> lefts = generateTrees(start, i - 1);
        List<TreeNode> rights = generateTrees(i + 1, end);
        for (TreeNode left : lefts) {
            for (TreeNode right : rights) {
                TreeNode node = new TreeNode(i);
                node.left = left;
                node.right = right;
                list.add(node);
            }
        }
    }
 
    return list;
}

http://gongxuns.blogspot.com/2013/01/leetcodeunique-binary-search-trees-ii.html

    public ArrayList<TreeNode> generateTrees(int a, int b){
        ArrayList<TreeNode> res = new ArrayList<TreeNode>();
        
        if(a>b){
            res.add(null);   
        }else if(a==b){//
            res.add(new TreeNode(a));
        }else{
            for(int i=a;i<=b;i++){
                ArrayList<TreeNode> temp1 = generateTrees(a,i-1);
                ArrayList<TreeNode> temp2 = generateTrees(i+1,b);
                
                for(TreeNode n:temp1){
                    for(TreeNode m:temp2){
                        TreeNode temp= new TreeNode(i);
                        temp.left=n;
                        temp.right=m;
                        res.add(temp);
                    }
                }

            }
        } 
        return res;
    }

https://zxi.mytechroad.com/blog/uncategorized/leetcode-95-unique-binary-search-trees-ii/
Time complexity: O(3^n)
Space complexity: O(3^n)

  public List<TreeNode> generateTrees(int n) {

    if (n == 0) return new ArrayList<TreeNode>();

    return generateTrees(1, n);

}

  private List<TreeNode> generateTrees(int l, int r) {

    List<TreeNode> ans = new ArrayList<>();

    if (l > r) {      

      ans.add(null);

      return ans;

}

    for (int i = l; i <= r; ++i)

      for (TreeNode left : generateTrees(l, i - 1))

        for (TreeNode right: generateTrees(i + 1, r)) {

          TreeNode root = new TreeNode(i);

          root.left = left;

          root.right = right;

          ans.add(root);

}

    return ans;

}

https://leetcode.com/discuss/39701/should-be-6-liner

def generateTrees(self, n):
    def node(val, left, right):
        node = TreeNode(val)
        node.left = left
        node.right = right
        return node
    def trees(first, last):
        return [node(root, left, right)
                for root in range(first, last+1)
                for left in trees(first, root-1)
                for right in trees(root+1, last)] or [None]
    return trees(1, n)

Or even just four lines, if it's not forbidden to add an optional argument:

def node(val, left, right):
    node = TreeNode(val)
    node.left = left
    node.right = right
    return node

class Solution:
    def generateTrees(self, last, first=1):
        return [node(root, left, right)
                for root in range(first, last+1)
                for left in self.generateTrees(root-1, first)
                for right in self.generateTrees(last, root+1)] or [None]

http://www.jiuzhang.com/solutions/unique-binary-search-trees-ii/
https://leetcode.com/discuss/31127/a-simple-bottom-up-dp-solution

LeetCode 95 - Unique Binary Search Trees II

Labels

Popular Posts