P205. 用 1~n 生成二叉搜索树

https://algocasts.io/episodes/kVG9a2Gg

动态规划真难…看完思路之后,写了一版有点小出入。f(low,high)函数在low>high的时候,返回Collections.singletonList(null)正确,返回Collections.EMPTY_LIST结果错误
private List generateTrees(int low, int high) {
if (low > high) return Collections.singletonList(null);
if (low == high) return Collections.singletonList(new TreeNode(low));

    List<TreeNode> resultList = new ArrayList<>();

    for (int i = low; i <= high; i++) {
        List<TreeNode> lefts = generateTrees(low, i - 1);
        List<TreeNode> rights = generateTrees(i + 1, high);
        for (TreeNode right : rights) {
            for (TreeNode left : lefts) {
                TreeNode root = new TreeNode(i);
                root.left = cloneTree(left);
                root.right = cloneTree(right);
                resultList.add(root);
            }
        }
    }
    return resultList;
}