“This is the 16th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

preface

The different binary search trees in question 96 are shown below:

Given an integer n, how many binary search trees are composed of exactly n nodes with different values from 1 to n? Returns the number of binary search tree species that satisfy the problem.

Example 1:

Input: n = 3 Output: 5Copy the code

A, thinking

This problem than the previous problem is different: only care about the tree of the binary search tree, but not the tree node.

So my idea at the beginning was to do it recursively, to get rid of the part that kept the path, and just get the number of left children and the number of right children. 7 The code is as follows:

public int dfs(int start, int end) {
    int ret = 0;
    if (start > end) {
        return 1;
    }
    // Enumerate viable root nodes
    for (int i = start; i <= end; i++) {
        // Find all left subtrees
        int left = dfs(start, i - 1);

        // Find all right subtrees
        int right = dfs(i + 1, end);
        ret += left * right;
    }
    return ret;
}
Copy the code

Unfortunately, n=18 will prompt you to exceed the time limit!

So since you can’t recurse from the top down, you have to use dynamic programming to do bottom-up.

First of all, let’s look at where we call it in the recursion, and we see that in the recursion we’re always looking at the number of left and right children from 1 to i-1 and I +1 to n.

Let dp[I] be the number of different binary search trees of length I.

There can be a dp [n] = dp [0] dp [n – 1) + dp [1] dp [n – 2) + dp [2] dp [n – 3) +… + dp[n-1]dp[0]

The formula explains: because dp[n] is to choose an element I in 1 ~ n as the root, and then take the element from 1 ~ I -1 as the left child, and the element from I +1 ~ n as the right child. Dp [0]dp[n-1] is the number of possible results of choosing the first element as the root. In addition, because of the particularity of binary search tree. The binary search tree of 1, 2, 3 and 1, 2, 4 has the same number of species. Therefore, we can ignore the value of elements in the formula and only focus on the number of elements, because the binary search tree with the same number of elements has the same type of tree.

Second, the implementation

The implementation code

The implementation code is consistent with the idea

    public int numTrees(int n) {
        int[] dp = new int[n +1];
        dp[0] = dp[1] = 1;  // There is only one result for both 0 and 1 elements
        for (int i=2; i<= n; i++) {
            for (int j=1; j<=i; j++) {
                dp[i] += dp[j-1] * dp[i-j]; }}return dp[n];
    }
Copy the code

The test code

    public static void main(String[] args) {
        int ret = new Number96().numTrees(3);
        System.out.println(ret);
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section