[LeetCode每日一题]95. Unique Binary Search Trees II
2020/3/7大约 1 分钟
题目如下:
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.
Example:
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
95. Unique Binary Search Trees II 给定一个自然数n,找出所有由1-n组成的不同的二叉搜索树。这是这个系列的第二道题,这道题同样可以用动态规划解决。dp[i]存储由1i组成的所有二叉搜索树,怎样求这样的二叉搜索树呢?首先1i都可以作为BST的根节点,假设以r为根,则r的左子树为1(r-1)组成的BST;右子树为(r+1)i组成的BST,该右子树可由1~(i-r)组成的BST每个节点均增加r得来。由此计算,可得dp[n]是原问题的解。 实现代码如下:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List generateTrees(int n) {
if (n == 0) {
return new ArrayList<>();
}
List[] dp = new ArrayList[n + 1];
dp[0] = new ArrayList<>();
dp[0].add(null);
dp[1] = new ArrayList<>();
TreeNode root = new TreeNode(1);
dp[1].add(root);
for (int len = 2; len <= n; len++) {
dp[len] = new ArrayList<>();
for (int r = 1; r <= len; r++) {
for (TreeNode left : dp[r - 1]) {
int remain = len - r;
for (TreeNode right : dp[remain]) {
TreeNode node = new TreeNode(r);
node.left = left;
node.right = doOffset(right, r);
dp[len].add(node);
}
}
}
}
return dp[n];
}
private TreeNode doOffset(TreeNode root, int offset) {
if (root == null) {
return null;
}
TreeNode node = new TreeNode(root.val + offset);
node.left = doOffset(root.left, offset);
node.right = doOffset(root.right, offset);
return node;
}
}