Java 2ms recursive with memoization, and 3ms DP


  • 1
    Y

    Recursive with memoization, very intuitive

    public class Solution {
        public List<TreeNode> generateTrees(int n) {
            List<TreeNode>[][] treesForRange = (ArrayList<TreeNode>[][]) new ArrayList[n+2][n+1];
            helper(1, n, treesForRange);
            return treesForRange[1][n];
        }
        
        private void helper(int left, int right, List<TreeNode>[][] treesForRange) {
            if (treesForRange[left][right] != null) {
                return;
            }
            treesForRange[left][right] = new ArrayList<TreeNode>();
            if (left > right) {
                treesForRange[left][right].add(null);
            }
            for (int root = left; root <= right; root++) {
                helper(left, root - 1, treesForRange);
                helper(root + 1, right, treesForRange);
                for (TreeNode leftNode : treesForRange[left][root-1]) {
                    for (TreeNode rightNode : treesForRange[root+1][right]) {
                        TreeNode rootNode = new TreeNode(root);
                        rootNode.left = leftNode;
                        rootNode.right = rightNode;
                        treesForRange[left][right].add(rootNode);
                    }
                }
            }
        }
    }
    

    DP solution: basic idea is same as the previous recursive solution. It looks more lengthy and ugly, yet may save us from stack overflow.

    public class Solution {
        public List<TreeNode> generateTrees(int n) {
            // DP, compute and store trees for intermediate ranges from 1 to n
            // time: exponential, since for each range the number of trees is combinatorial
            // space: O(n^2)
            if (n == 0) {
                List<TreeNode> result = new ArrayList<TreeNode>();
                result.add(null);
                return result;
            }
            List<TreeNode>[][] treesForRange = (ArrayList<TreeNode>[][]) new ArrayList[n+2][n+1];
            for (int step = 0; step < n; step++) {
                for (int i = 1; i <= n - step; i++) {
                    int j = i + step;
                    treesForRange[i][j] = new ArrayList<TreeNode>();
                    if (step == 0) {
                        treesForRange[i][j].add(new TreeNode(i));
                        continue;
                    }
                    // k is a possible root for range i-j
                    for (int k = i; k <= j; k++) {
                        // two ugly if blocks for boundary cases:
                        // when k == i, the left subtree is null
                        // when k == j, the right subtree is null
                        if (treesForRange[i][k-1] == null) {
                            treesForRange[i][k-1] = new ArrayList<TreeNode>();
                            treesForRange[i][k-1].add(null);
                        }
                        if (treesForRange[k+1][j] == null) {
                            treesForRange[k+1][j] = new ArrayList<TreeNode>();
                            treesForRange[k+1][j].add(null);
                        }                    
                        for (TreeNode leftNode : treesForRange[i][k-1]) {
                            for (TreeNode rightNode : treesForRange[k+1][j]) {
                                TreeNode root = new TreeNode(k);
                                root.left = leftNode;
                                root.right = rightNode;
                                treesForRange[i][j].add(root);
                            }
                        }
                    }
                }
            }
            return treesForRange[1][n];
        }
    }

  • 0
    Y
    This post is deleted!

  • 0
    T

    You can simplify the "ugly ifs" with treesForRange[i][k-1] = Collections.singletonList(null);, this also triggers a runtime error, so you need to create a new List[][] which is good practice anyway since you're not using the fact that you store ArrayLists.

    Another way of making it nicer is to pre-fill the boundary cases before the step loop starts:

    List<TreeNode> emptyTree = Collections.singletonList(null); // immutable list
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            treesForRange[i][j-1] = emptyTree;
            treesForRange[j+1][i] = emptyTree;
        }
    }

Log in to reply
 

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