你的位置:首页 > Java教程

[Java教程]LeeCode


题目:

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

思路:

找规律

1. 没有节点,BST (Binary Search Tree)为1个, 即空树

2. 有一个节点,BST为1个,即自身为根节点

3. 有二个节点,BST为2个,1为root,左为空,右为2;2为root,左为1,右为空,其实就是dp[0]*dp[1] + dp[1]*dp[0]

      1                  2

        \               /

         2            1

4. 有三个节点

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

可以推出dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0]

package bst;public class UniqueBinarySearchTrees {  public int numTrees(int n) {    int[] dp = new int[n + 1];    dp[0] = 1;    dp[1] = 1;    for (int i = 2; i <= n; ++i) {      for (int j = 0; j < i; ++j) {        dp[i] += dp[j] * dp[i - 1 - j];      }    }    return dp[n];  }    public static void main(String[] args) {    // TODO Auto-generated method stub    UniqueBinarySearchTrees u = new UniqueBinarySearchTrees();    System.out.println(u.numTrees(3));  }}