Quite clean Java solution with explanation


  • 4
    W

    For all possible root of the trees (i.e. 1, 2, ..., n), get the list of left subtrees and list of right subtrees, recursively. Now, for every left and right subtree combination, create a new tree and add to resultant list.

    Here, "start > end" becomes the base case for recursion, for which I add "null" as the only element of list, which will form the only possible left or right subtree. (To understand why this works, check with n = 1).

    n = 0 is handled separately, since leetcode expects an empty list, rather than a list with a null value.

    public class Solution {
        public List<TreeNode> generateTrees(int n) {
            if(n == 0)
                return new ArrayList<TreeNode>();
            return generateTrees(1, n);
        }
        
        List<TreeNode> generateTrees(int start, int end) {
            List<TreeNode> result = new ArrayList<TreeNode>();
            if(start > end) {
                result.add(null);
                return result;
            }
            for(int i = start; i <= end; i++) {
                List<TreeNode> leftSubTrees = generateTrees(start, i - 1);
                List<TreeNode> rightSubTrees = generateTrees(i + 1, end);
                for(TreeNode left : leftSubTrees) {
                    for(TreeNode right : rightSubTrees) {
                        TreeNode root = new TreeNode(i);
                        root.left = left;
                        root.right = right;
                        result.add(root);
                    }
                }
            }
            return result;
        }
    }

Log in to reply
 

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