Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

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

分析

由于只是求个数，其实与数值无关，可以用DP解决。dp[i]表示i个点能组成的BST数量, 那么

dp[i] = dp[j]*d[i - 1 - j](j = 0,1...i-1)

这道题也可以有Follow up, 比如返回满足要求的所有不同的树，其实也是Leetcode原题Unique Binary Search Trees II

由于是返回所有的树，可以用recursion的方法，分别得到左右两边的所有的树，然后固定root, 用两个loop, 组合所有左右子树即可。

类似的构造所有树的问题都可以用类似recursion的方法。

复杂度

time: O(n^2), space: O(n)

代码

public class Solution {    public int numTrees(int n) {        int[] dp = new int[n + 1];        dp[0] = 1;        for (int i = 1; i <= n; i++) {for (int j = 0; j <= i - 1; j++) {    dp[i] += dp[j] * dp[i - 1 - j];}        }        return dp[n];    }}

Follow up

public class Solution {    public List<TreeNode> generateTrees(int n) {        if (n == 0) {return new ArrayList<TreeNode>();        }        return helper(1, n);    }        public List<TreeNode> helper(int start, int end) {        List<TreeNode> res = new ArrayList<>();        if (start > end) {res.add(null);return res;        }        for (int i = start; i <= end; i++) {List<TreeNode> left = helper(start, i - 1);List<TreeNode> right = helper(i + 1, end);for (TreeNode leftChild : left) {    for (TreeNode rightChild : right) {        TreeNode root = new TreeNode(i);        root.left = leftChild;        root.right = rightChild;        res.add(root);    }}        }        return res;    }}