95. Unique Binary Search Trees II

题目描述和难度

• 题目描述：

输入: 3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

• 题目难度：中等。
• 英文网址：95. Unique Binary Search Trees II 。
• 中文网址：95. 不同的二叉搜索树 II 。

思路分析

求解关键：

当前的递归中，假设 root为 i。 那么左子树是由 [1, i - 1] 构成的所有可能的组合，右子树是由 [i + 1, n] 构成的所有可能的组合。 可以统一记录为用 [start, end] 去构建一棵树。 在有了左子树、根结点、右子树的情况下，根据乘法原理很容易计算得出在当前情况下的所有的树。记录 root 到一个 vector 中就可以完整地记录所有结果，返回结果即可。

1、递归每次都返回一堆结点，而不是一个结点。 当递归的返回结果为多个时，为了方便处理，可以把这些结果打包放入一个 vector（列表）中。 2、是典型的 DFS 题目。

易错点在于，n = 0 时，我们对属于它的链表 res[0] 也要加入结点 null ，否则如果左子树需要 n = 0 的解集，而链表为空， 则会直接跳过里面对右子树的访问。所以我们需要加入一行 res[0].add(null); 这样就能解决此问题。

参考解答

参考解答1

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

/**
 * 典型的使用分治思想解决的问题
 */
public class Solution {

    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> res = new ArrayList<>();
        if (n <= 0) {
            return res;
        }
        return generateTrees(1, n);
    }

    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> res = new ArrayList<>();
        if (start > end) {
            // 上层调用的方法须要这个空结点作为其左结点或者右节点
            res.add(null);
            return res;
        } else if (start == end) {
            // 只有一个结点，这个结点作为根结点返回即可
            // 这一步可以包括到下面一个情况中
            res.add(new TreeNode(start));
            return res;
        } else {
            for (int i = start; i <= end; i++) {
                List<TreeNode> leftList = generateTrees(start, i - 1);
                List<TreeNode> rightList = generateTrees(i + 1, end);
                for (TreeNode l : leftList) {
                    for (TreeNode r : rightList) {
                        TreeNode root = new TreeNode(i);
                        root.left = l;
                        root.right = r;
                        res.add(root);
                    }
                }
            }
        }
        return res;
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0095-unique-binary-search-trees-ii ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。