My java solution


  • 0
    S
    public class Solution {
    
    
    public class Result
    {
        List<TreeNode> nodes;
        
        public Result(List<TreeNode> list)
        {
            this.nodes=list;
        }
    }
    
    public List<TreeNode> generateTrees(int n) {
        if(n<=0) 
        {
            List<TreeNode> r  = new ArrayList<TreeNode>();
            r.add(null);
            return r;
        }
        Result[][] mem=new Result[n+2][n+2];
        for(int i =0;i<=n+1;i++)
        {
            for(int j=0;j<=n+1;j++)
            {
                if(i>j)
                {
                    mem[i][j]=new Result(new ArrayList<TreeNode>());
                }
            }
        }
        for(int len =0;len<n;len++)
        {
            for(int start=1;start<=n;start++)
            {
                int end=start+len;
                if(end<=n)
                {
                    List<TreeNode> nodes = new ArrayList<TreeNode>();
                    for(int t=start;t<=end; t++)
                    {
                        List<TreeNode> left=mem[start][t-1].nodes;
                        List<TreeNode> right=mem[t+1][end].nodes;
                        if(!left.isEmpty()&&!right.isEmpty())
                        {
                            for(int j=0;j<left.size();j++)
                            {
                                for(int k=0;k<right.size();k++)
                                {
                                    TreeNode tn = new TreeNode(t);
                                    tn.left=left.get(j);
                                    tn.right=right.get(k);
                                    nodes.add(tn);
                                }
                            }
                        }
                        else if(!left.isEmpty())
                        {
                            for(TreeNode nn:left)
                            {
                                TreeNode tn = new TreeNode(t);
                                tn.left=nn;
                                nodes.add(tn);
                            }
                        }
                        else if(!right.isEmpty())
                        {
                            for(TreeNode nn:right)
                            {
                                TreeNode tn = new TreeNode(t);
                                tn.right=nn;
                                nodes.add(tn);
                            }
                        }
                        else
                        {
                            nodes.add(new TreeNode(t));
                        }
                    }
                    mem[start][end]=new Result(nodes);  
                }
                    
                    
            }
        }
        return mem[1][n].nodes;
    }
    

    }


Log in to reply
 

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