Leetcode(95) Unique Binary Search Trees II

发表于 | 更新于 | 分类于

Description

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

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

解法

这道题是基于之前算有多少棵不同的树的。对于此类问题，一般采用递归解法。首先，对于一棵BST树的某节点而言，其左子树的所有节点值一定是小于其右子树的所有节点值的。故对于1到n的序列，可以选择一块范围为1到n的挡板将序列分为[1..i-1],i,[i+1,n]三部分，i为根，其他为左右子树的节点，然后对于左右子树递归地进行操作。注意，设计的函数的返回值是一个x棵子树根节点的List，每次只需将根节点插入其中即可。而对于一个根节点，可以从其左右子树的根序列中选取根节点作为左右的儿子，而以此达到遍历所有情况的目的。

具体代码如下：

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
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }

        return helper(1, n);
    }

    List<TreeNode> helper(int start, int end) {
        List<TreeNode> result = new ArrayList<>();
        if (start > end) {
            result.add(null);
            return result;
        }
        for (int i = start; i <= end; i++) {
            List<TreeNode> left = helper(start, i - 1);
            List<TreeNode> right = helper(i + 1, end);
            for (int j = 0; j < left.size(); j++) {
                for (int k = 0; k < right.size(); k++) {
                    TreeNode root = new TreeNode(i);
                    root.left = left.get(j);
                    root.right = right.get(k);
                    result.add(root);
                }
            }
        }
        return result;
    }
}