Accepted recursive solution with hashmap optmization.


  • 0
    C
    public class Solution {
        HashMap<Integer, ArrayList<ArrayList<TreeNode>>>map = new HashMap<>();
        public List<TreeNode> generateTrees(int n) {
            ArrayList<TreeNode> list = new ArrayList<>();
            list.add(null);
            if(n==0)return list;
            return gen(1, n);
        }
        private ArrayList<TreeNode> gen(int s, int e){
            ArrayList<TreeNode> list;
            if(e==s){
                list=new ArrayList<>();
                list.add(new TreeNode(s));
                return list;
            }
            if(map.containsKey(e-s)&&map.get(e-s).size()>=s){
                return map.get(e-s).get(s-1);
            }
            list = new ArrayList<>();
            for(int i=e; i>=s; i--){
                ArrayList<TreeNode> leftList;
                if(i>s)leftList=gen(s, i-1);
                else{
                    leftList=new ArrayList<>();
                    leftList.add(null);
                }
                ArrayList<TreeNode> rightList;
                if(i+1<=e)rightList = gen(i+1, e);
                else{
                    rightList=new ArrayList<>();
                    rightList.add(null);
                }
                for(int l=0; l<leftList.size(); l++){
                    for(int r=0; r<rightList.size(); r++){
                        TreeNode root = new TreeNode(i);
                        root.left=leftList.get(l);
                        root.right=rightList.get(r);
                        list.add(root);
                    }
                }
            }
            ArrayList<ArrayList<TreeNode>> mapList;
            if(map.containsKey(e-s)){
                mapList=map.get(e-s);
                mapList.add(list);
            }
            else{
                mapList= new ArrayList<>();
                mapList.add(list);
                map.put(e-s, mapList);
            }
            
            return list;
        }
    }

  • 0
    Y

    could you explain what are arguments s and e in the gen function and what the meaning of second argument in map type?


  • 0
    C

    the gen function generates all binary trees from s to e. the map stores previously found tree structure based on the number of nodes in a List<List<TreeNode> . then it is further indexed by the value of the head node.

    i hope that helps


Log in to reply
 

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