Java Solution with DP


  • 105
    J

    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.


  • 3
    B

    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 class Solution {
    	TreeNode deepCopy(TreeNode root){
    		if(root == null) return null;
    		TreeNode tmp = new TreeNode(1);
    		tmp.left = deepCopy(root.left);
    		tmp.right = deepCopy(root.right);
    		return tmp;
    	}
    	int cur = 0;
    	void setValue(TreeNode root){
    		if(root.left != null){
    			setValue(root.left);
    		}
    		root.val = cur++;
    		if(root.right != null){
    			setValue(root.right);
    		}
    		
    	}
        public List<TreeNode> generateTrees(int n) {
        	if(n <= 0){
        		List<TreeNode> res =new ArrayList<TreeNode>();
        		res.add(null);
        		return res;
        	}
        	
            List<TreeNode>[] dp = new ArrayList [n+1];
            for(int i = 0; i < n+1; ++i){
            	dp[i] =  new ArrayList<TreeNode>();
            }
            
            dp[0].add(null);
            
            for(int i = 1; i <= n; ++i){
            	for(int j = 0; j < i; ++j){
            		for(int k = 0; k < dp[j].size(); ++k){
            			for(int l = 0; l < dp[i-1-j].size(); ++l){
            				TreeNode tmp = new TreeNode(1);
            				tmp.left = deepCopy(dp[j].get(k));
            				tmp.right = deepCopy(dp[i-1-j].get(l));
            				dp[i].add(tmp);
            			}
            		}
            	}
            }
            
            for(int i = 0; i < dp[n].size(); ++i){
            	cur = 1;
            	setValue(dp[n].get(i));
            }
            return dp[n];
        }
    }

  • 0
    O

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


  • 8
    J

    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;


  • 0

    This is brilliant!
    Thanks for sharing!


  • 0
    L

    Great solution, thanks!


  • 0
    L

    The corner case you handle is wrong. If you write as res.add(null), it will be an array of array. Just comment that line. You will be fine :-)


  • 0
    J

    @blue_y This is indeed so much better to understand !


  • 0
    Y

    But how do you solve the n = 0 condition? your code returns [[]] for n = 0 but OJ requires []. So actually it cannot pass OJ.


  • 0
    S

    same to @jayesch question,if n==0,your cod will return [[]] and failed.


  • 0
    J

    @shangmingyang seems they changed the expected result after I submit the answer two years ago. In my opinion both are valid. I have adjusted the code to comply to the new result.


  • 0
    N

    I was thinking about the clone idea when trying to solve this problem. Then I asked myself, is it really more efficient by doing clone (and it'a "deep" clone) compared to simply construct the tree on the right side? I think they are the same after a second thought.
    Anyone can help take a look at my question?


  • 0
    A

    elegant offset~:D


  • 0
    C

    I got exactly same idea. May I give a little suggestion? I think putting left side loop inside of right side will reduce number of clone execution.


  • 0
    Q

    This offset idea is really distinctive.


  • 3

    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)

    public List<TreeNode> generateTrees(int n) {
    	
    	List<TreeNode>[] res = new List[n+1];
    	res[0] = new ArrayList();
    	if(n == 0) return res[0];
    	res[0].add(null);
    	res[1] = new ArrayList();
    	res[1].add(new TreeNode(1));
    	for(int i=2;i<=n;i++){
    	    res[i] = new ArrayList();
    		for(int j=1;j<=i;j++){
    			for(TreeNode nodeL: res[j-1]){
    				for(TreeNode nodeR: res[i-j]){
    					TreeNode node = new TreeNode(j);
    					node.left = nodeL;
    					node.right = clone(nodeR, j);
    					res[i].add(node);
    				}
    			}
    		}
    	}
    	return res[n];
    }
    
    
    static TreeNode clone(TreeNode node, int offset){
    	if(node == null) return null;
    	TreeNode newNode = new TreeNode(node.val + offset);
    	newNode.left = clone(node.left, offset);
    	newNode.right = clone(node.right, offset);
    	return newNode;
    }
    

  • 0
    Y

    @Lucifer92_ I think null can represent a null TreeNode also.


  • 0
    P

    What's the time complexity of the algorithm?
    The difficulty is the time complexity of inner most two loops.


  • 0
    Y

    @peace 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!)


  • 0
    P

    @YaokaiYang How (2n)!/((n+1)!n!) comes? Could you explain the process of computation?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.