My JAVA recursive solution--how to get the DP idea?


  • 0
    Y
    public class Solution {
    public List<TreeNode> generateTrees(int n) {
        
        List<TreeNode> contanier =new ArrayList<TreeNode>();
        
        if (n<=0)  {
              contanier.add(null);
              return contanier;
            }
        
        if (n==1){
            contanier.add(new TreeNode(n));
            return contanier;
        }
        
        //recursive method using 1 as root, 2 as root, 3 as root, ...
        //and n as root
        for (int i=1; i<=n; i++){
            TreeNode head=new TreeNode(i);
            
            //for each i, get the left and right sub-trees, returns are the List
            List<TreeNode> fromLeft=buildTree(1, i-1);
            List<TreeNode> fromRight=buildTree(i+1, n);
            
            //construct the final trees. if left sub-tree has N possibilities, right sub-tree has 
            //M possibilities, the final tree will have N*M possibilities.
            for (int j=0; j<fromLeft.size(); j++){
                for (int k=0; k<fromRight.size(); k++){
                    TreeNode temp=new TreeNode(i);
                    temp.left=fromLeft.get(j);
                    temp.right=fromRight.get(k);
                    contanier.add(temp);
                }
            }
        }
        
        return contanier;
        
    }
    
    public List<TreeNode> buildTree(int s, int e){
        List<TreeNode> con =new ArrayList<TreeNode>();
        
        if (e<s) {
            con.add(null);
            return con;
        }
        if (e==s){
            con.add(new TreeNode(s));
            return con;
        }
        
        for (int i=s; i<=e; i++){
            TreeNode head=new TreeNode(i);
            List<TreeNode> fromLeft=buildTree(s, i-1);
            List<TreeNode> fromRight=buildTree(i+1, e);
            for (int j=0; j<fromLeft.size(); j++){
                for (int k=0; k<fromRight.size(); k++){
                    TreeNode temp=new TreeNode(i);
                    temp.left=fromLeft.get(j);
                    temp.right=fromRight.get(k);
                    con.add(temp);
                }
            }
        }
        
        return con;
        
    }
    

    }


Log in to reply
 

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