Divide-and-conquer. F(i) = G(i-1) * G(n-i)


  • 77
    L

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

  • 0
    X

    Seems it is not a DP, but just a divide-and-conquer one. Because algorithm could generate the same subtree for twice as it did not record the tree it generated before.


  • 1
    L

    Yes, it is a divide-and-conquer solution, as I mentioned in the title of this post.


  • 0
    X

    Sorry, I misread your words.


  • 1
    J

    I tried your code and found when input n is 0, the expected output is [], but yours is [[]]. I think you need to add just one case control.


  • 2
    D

    add one line case control as following is accepted

    public List<TreeNode> generateTrees(int n) {

    if(n==0) return new LinkedList<TreeNode>(); //here is new line

    return generateSubtrees(1, n);

    }


  • 0
    G

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

    public class Solution {

    Map<List<Integer>,List<TreeNode>> hm = new HashMap<>();
    
    
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> res = new LinkedList<TreeNode>();
        if(n == 0) return res;
        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<Integer> leftIndex = new ArrayList<>();
            leftIndex.add(s);
            leftIndex.add(i-1);
            List<Integer> rightIndex = new ArrayList<>();
            rightIndex.add(i+1);
            rightIndex.add(e);
            List<TreeNode> leftSubtrees,rightSubtrees;
            if(hm.get(leftIndex) == null){
                leftSubtrees = generateSubtrees(s, i - 1);
                hm.put(leftIndex,leftSubtrees);
            }
            else leftSubtrees = hm.get(leftIndex);
    
            if(hm.get(rightIndex) == null){
                rightSubtrees = generateSubtrees(i + 1, e);
                hm.put(rightIndex,rightSubtrees);
            }
            else rightSubtrees = hm.get(rightIndex);
    
    
    
            for (TreeNode left : leftSubtrees) {
                for (TreeNode right : rightSubtrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    res.add(root);
                }
            }
        }
        return res;
    }
    

    }


  • 0
    S

    how would you think its complexity?


  • 1
    Y

    @Scarlett_comeup
    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)$


  • 0
    Z

    Why we really the case: if(s > e)? I tried run the code without this case. Then I get the empty list for final result. Could anyone tell me why it is that?


  • 0
    V

    @liaison can you please explain how recursion works here exactly? It is little difficult to visualize how all the trees will be generated from this.


  • 0
    M

    @YaokaiYang Catalan number Cn ~4^n/n^(3/2). I agree with exponential complexity.


Log in to reply
 

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