0%

leetcode每日一题-不同的二叉搜索树II

Posted on In ,

不同的二叉搜索树II

image1

方法一：递归

二叉搜索树关键的性质是根节点的值大于左子树所有节点的值，小于右子树所有节点的值，且左子树和右子树也同样为二叉搜索树。因此在生成所有可行的二叉搜索树的时候，假设当前序列长度为 nn，如果我们枚举根节点的值为 $i$，那么根据二叉搜索树的性质我们可以知道左子树的节点值的集合为 $[1 \dots i-1]$，右子树的节点值的集合为 $[i+1 \dots n]$。而左子树和右子树的生成相较于原问题是一个序列长度缩小的子问题，因此我们可以想到用递归的方法来解决这道题目。

我们定义generateTrees(start, end)函数表示当前值的集合为$[start, end]$，返回序列$[start,end]$生成的所有可行的二叉搜索树。按照上文的思路，我们考虑枚举$[start,end]$中的值 $i$为当前二叉搜索树的根，那么序列划分为了 $[start,i-1]$和 $[i+1,end]$ 两部分。我们递归调用这两部分，即 generateTrees(start, i - 1) 和 generateTrees(i + 1, end)，获得所有可行的左子树和可行的右子树，那么最后一步我们只要从可行左子树集合中选一棵，再从可行右子树集合中选一棵拼接到根节点上，并将生成的二叉搜索树放入答案数组即可。

递归的入口即为 generateTrees(1, n)，出口为当$start > end$ 的时候，当前二叉搜索树为空，返回空节点即可。

1
/**
2
 * Definition for a binary tree node.
3
 * public class TreeNode {
4
 *     int val;
5
 *     TreeNode left;
6
 *     TreeNode right;
7
 *     TreeNode() {}
8
 *     TreeNode(int val) { this.val = val; }
9
 *     TreeNode(int val, TreeNode left, TreeNode right) {
10
 *         this.val = val;
11
 *         this.left = left;
12
 *         this.right = right;
13
 *     }
14
 * }
15
 */
16
class Solution {
17
    public List<TreeNode> generateTrees(int n) {
18
        if (n == 0) {
19
            return new LinkedList<TreeNode>();
20
        }
21
        return generateTrees(1, n);
22
    }
23
24
    public List<TreeNode> generateTrees(int start, int end) {
25
        List<TreeNode> allTrees = new LinkedList<TreeNode>();
26
        if (start > end) {
27
            allTrees.add(null);
28
            return allTrees;
29
        }
30
31
        // 枚举可行根节点
32
        for (int i = start; i <= end; i++) {
33
            // 获得所有可行的左子树集合
34
            List<TreeNode> leftTrees = generateTrees(start, i - 1);
35
36
            // 获得所有可行的右子树集合
37
            List<TreeNode> rightTrees = generateTrees(i + 1, end);
38
39
            // 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
40
            for (TreeNode left : leftTrees) {
41
                for (TreeNode right : rightTrees) {
42
                    TreeNode currTree = new TreeNode(i);
43
                    currTree.left = left;
44
                    currTree.right = right;
45
                    allTrees.add(currTree);
46
                }
47
            }
48
        }
49
        return allTrees;
50
    }
51
}

复杂度分析：

  • 时间复杂度：整个算法的时间复杂度取决于「可行二叉搜索树的个数」，而对于 n个点生成的二叉搜索树数量等价于数学上第 n个「卡特兰数」，用 $G_n$表示。生成一棵二叉搜索树需要$O(n)$的时间复杂度，一共有$G_n$棵二叉搜索树，也就是 $O(nG_n)$。而卡特兰数以 $\frac{4^n}{n^{3/2}}$增长，因此总时间复杂度为 $O(\frac{4^n}{n^{1/2}})$。
  • 空间复杂度：n 个点生成的二叉搜索树有 $G_n$棵，每棵有 n 个节点，因此存储的空间需要$ O(nG_n) = O(\frac{4^n}{n^{1/2}})$
    ，递归函数需要 $O(n)$的栈空间，因此总空间复杂度为 $O(\frac{4^n}{n^{1/2}})$。