LeetCode95-不同的二叉搜索树II

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/unique-binary-search-trees-ii/

中文链接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii/

题目详述

给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入: 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

题目详解

LeetCode96-不同的二叉搜索树 是求以 1 … n 为节点组成的二叉搜索树的方案种数，而本题则是求出所有的方案。解题思路是一致的。

方法一：直接进行搜索。

  • 传入两个参数，用于表示范围，便于直接生成结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class LeetCode_00095 {

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

    private List<TreeNode> dfs(int l, int r) {
        List<TreeNode> res = new ArrayList<>();
        if (l > r) {
            res.add(null);
            return res;
        }
        for (int i = l; i <= r; ++i) {
            List<TreeNode> leftList = dfs(l, i - 1);
            List<TreeNode> rightList = dfs(i + 1, r);
            for (TreeNode left : leftList) {
                for (TreeNode right : rightList) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    res.add(root);
                }
            }
        }
        return res;
    }
}

方法二：动态规划

  • 外层循环代表从 dp[1] 推进到 dp[n]。
  • 内层循环用于计算当前 dp[i]。
  • dp[i] 的左子树部分，它是由 1 … j - 1 的结点生成的，可以直接复用之前生成的二叉搜索树。
  • dp[i] 的右子树部分，它是由 j + 1 … i 的结点生成的，运用之前生成的二叉搜索树的结构，加上偏移量 j 后得到新的二叉搜索树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class LeetCode_00095 {

    public List<TreeNode> generateTrees(int n) {
        if (n < 1) {
            return new ArrayList<>();
        }
        List<TreeNode>[] dp = new List[n + 1];
        dp[0] = new ArrayList<>();
        dp[0].add(null);
        for (int i = 1; i <= n; i++) {
            dp[i] = new ArrayList<>();
            for (int j = 1; j <= i; j++) {
                for (TreeNode left : dp[j - 1]) {
                    for (TreeNode right : dp[i - j]) {
                        TreeNode node = new TreeNode(j);
                        node.left = left;              // 复用
                        node.right = copy(right, j);   // 加上偏移量复制一份
                        dp[i].add(node);
                    }
                }
            }
        }
        return dp[n];
    }

    private TreeNode copy(TreeNode root, int offset) {
        if (root == null) {
            return null;
        }
        TreeNode node = new TreeNode(root.val + offset);
        node.left = copy(root.left, offset);
        node.right = copy(root.right, offset);
        return node;
    }
}