95. Unique Binary Search Trees II

Version #2 DP[TODO]

Version #1 Recursion
三刷
91.35 %
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) return new ArrayList<>();
        return dfs(1, n);
    }
   
    private List<TreeNode> dfs(int start, int end) {
        List<TreeNode> result = new ArrayList<>();
        if (start > end) {
            result.add(null);
            return result;
        }
        if (start == end) {
            result.add(new TreeNode(start));
            return result;
        }
        for (int i = start; i <= end; i++) {
            List<TreeNode> left = dfs(start, i - 1);
            List<TreeNode> right = dfs(i + 1, end);
            for (TreeNode l : left) {
                for (TreeNode r : right) {
                    TreeNode curr = new TreeNode(i);
                    curr.left = l;
                    curr.right = r;
                    result.add(curr);
                }
            }
        }
        return result;
    }
}

二刷
89.35 %
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n <= 0) {
            return new ArrayList<>();
        }
        // given a range, select a root
        return dfs(1, n);
    }
    private List<TreeNode> dfs(int start, int end) {
        if (start > end) {
            return Collections.singletonList(null);
        }
        if (start == end) {
            return Collections.singletonList(new TreeNode(start));
        }
        List<TreeNode> result = new ArrayList<>();
        for (int i = start; i <= end; i++) {
            List<TreeNode> left = dfs(start, i - 1);
            List<TreeNode> right = dfs(i + 1, end);
            for (TreeNode l : left) {
                for (TreeNode r : right) {
                    TreeNode root = new TreeNode(i);
                    root.left = l;
                    root.right = r;
                    result.add(root);
                }
            }
        }
        return result;
    }
}

一刷
 48.52 %
public class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> result = new ArrayList<>();
        if (n <= 0) return result;
        //TODO
        return generateTrees(1, n);
    }
    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> subResult = new ArrayList<>();
        if (start > end) {
            subResult.add(null);
            return subResult;
        }
        if (start == end) {
            subResult.add(new TreeNode(start));
            return subResult;
        }
        List<TreeNode> left, right;
        for (int mid = start; mid <= end; mid++) {
            left = generateTrees(start, mid - 1);
            right = generateTrees(mid + 1, end);
            for (TreeNode l : left) {
                for (TreeNode r : right) {
                    TreeNode root = new TreeNode(mid);
                    root.left = l;
                    root.right = r;
                    subResult.add(root);
                }
            }
        }
        return subResult;
    }
}