Java recursive solution.


  • 1
    S
    public class Solution {
        public List<TreeNode> generateTrees(int n) {
            return generateTrees(1, n);
        }
        
        private List<TreeNode> generateTrees(int m, int n){
            if(m > n) {
                List<TreeNode> result = new ArrayList<TreeNode>();
                result.add(null);
                return result;
            }
            List<TreeNode> roots = new ArrayList();
            for(int i = m; i <= n; i++){
                List<TreeNode> left = generateTrees(m, i-1);
                List<TreeNode> right = generateTrees(i+1, n);
                for(TreeNode l : left){
                    for(TreeNode r : right){
                        TreeNode root = new TreeNode(i);
                        root.left = l;
                        root.right = r;
                        roots.add(root);
                    }
                }
                
            }   
            return roots;
        }
    }

Log in to reply
 

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