Leetcode (3)

Topic:Different binary search trees

Description: Given an integer, in order toHow many kinds of binary search trees are there for nodes?

The sample

Input: 3 Output: 5 Explanation: Given n = 3, there are five binary search trees with different structures: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3Copy the code

Solution 1: dynamic programming

Ideas:

Given an ordered sequenceTo build a binary search tree, each number can be traversed, take the number as the root, willThe sequence, as the left subtree, willAs a right subtree, the left and right subtrees can then be constructed recursively in the same way.

plan

Define two functions

1. Length ofThe number of binary search trees that can be formed by the sequence of.
2. 以 Is the root, and the sequence length isThe number of different binary search trees 。

easy

For a given sequence, we choose numbersIs the root, then the root isThe set of all binary search trees is the set of left and right subtreesThe cartesian product

That is:

It can be concluded that:

For boundary conditions, when the sequence length is(only root) or for(empty tree), there is only one case, that is:

The code implementation is as follows:

public static int numTrees(int n) {
    int[] ints = new int[n + 1];
    ints[0] = 1;
    ints[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            ints[i] += ints[j - 1]*ints[i - j]; }}return ints[n];
}
Copy the code

• Time complexity: ，Indicates the number of nodes in the binary search tree
• Space complexity:

Solution 2: Math

Ideas:

In solution one, it goes outThe value of a function is mathematically calledQatar number . The Catalan number has the following properties:

That is:

public static int numTrees(int n) {
    long c = 1;
    for (int i = 2; i <= n; i++) {
        // Do not use *=, otherwise there will be an exception due to the omission of decimal
        c = c*2* (2*i - 1)/(i + 1);
    }
    return (int)c;
}
Copy the code

• Time complexity: ，Indicates the number of nodes in the binary search tree
• Space complexity: