3ms Java recursion solution


  • 0
    S
     public List<TreeNode> generateTrees(int n) {
        //memorized search should not be used here! 
    
      
        List<TreeNode> ans = new ArrayList<>();
        if (n == 0) {
            return ans;
        }
        return helper(1, n);
    }
    private List<TreeNode> helper(int start, int end) {
        List<TreeNode> ans = new ArrayList<>();
        if (start > end) {
            ans.add(null);
            return ans;
        }
        for (int i = start; i <= end; i++) {
            List<TreeNode> leftNodes = helper(start, i - 1);
            List<TreeNode> rightNodes = helper(i + 1, end);
            for (TreeNode left : leftNodes) {
                for (TreeNode right : rightNodes) {
                    TreeNode root = new TreeNode(i);   // Pay attention here!
                    root.left = left;
                    root.right = right;
                    ans.add(root);
                }
            }
        }
        return ans;
    }

Log in to reply
 

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