This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Title Description

Different binary search trees

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.

Second, train of thought analysis

  • So this is still dynamic programming. At first glance, this topic is easy to attract attention by the topic is mistaken for a binary tree test point. It’s really just using the shell of a binary tree and it’s dynamic programming inside.

Why dynamic programming

  • Why am I talking about dynamic programming? Because they didn’t ask us to iterate through the binary tree or use the properties of the binary tree. They’re just using the property that binary trees are two branches
  • We can interpret the problem as follows. Take a binomial tree at N nodes and find out how many ways there are.
  • A binary tree will only have two branches. When we know the number of binary trees formed by n-1 nodes, N nodes are twice as many as n-1 nodes for balancing and other operations. So N and N minus 1 are related
  • That’s why I say this is the test of dynamic programming

Formal analysis of

  • Since it is dynamic programming, so we are still the original three axe. Conversion equation — “initial value –” calculation

Transformation equation

  • Binary trees are left and right subtrees, so let’s say the current number of nodes is zerom. thenm-1The number of binary trees consisting of five nodes is F(m-1). And by them-1A binary tree consisting of two nodes can be in the firstmTo the left of a node, or to the right of it.

  • So F of m is at least 2 times F of m minus 1. But the number of nodes below m is not just m minus one. And the m – 2.
  • At this point, we divide m-1 into two heaps, such as k and M-1-K. And the possibility of k nodes forming a binary tree is called F of k, and the possibility of m minus 1 minus k is called F of m minus 1 minus k.
  • The k and M-1-K piles correspond to M nodes as its left and right subtrees respectively. Some of you here might think you can switch right and left and it should be twice as much. Here we have k going from 1 to m minus 2. So we don’t need twice that

  • Join us and the m node is 5. Then the left subtree of our m=5 node will have the following situation F(1),F(2),F(3), while the right subtree corresponds to F(3),F(2),F(1) respectively.

  • So F of m has all the sums of F of k times F of m minus 1, in addition to 2 times F of m minus 1. The k range here is 1<=k<=m-1-1.

  • Finally we can determine the following conversion equation


f ( x ) = 2 ⋅ f ( x – 1 ) + f ( 1 ) ⋅ f ( x – 2 ) + f ( 2 ) ⋅ f ( x – 3 ) + … + f ( x – 2 ) ⋅ f ( 1 ) f(x)=2 \cdot f(x-1)+f(1)\cdot f(x-2)+f(2) \cdot f(x-3)+\cdots+f(x-2) \cdot f(1)

The initial value

  • A binary tree has no binary tree if it has no nodes, and a binary tree has one node. soF(0)=0 ; F(1) = 1 。

There are small to large calculations

  • You have an initial value, and there’s no condition for the transformation equation. So this one, as long as you sort out the equations, the rest will be pretty easy

AC code

  • It’s easy to derive it based on the above equation and the initial values, but the derivation will use all the previous cases. So here we need to create a new array to maintain a count for each state

int[] arr = new int[n];
Copy the code

  • For our sake, let’s create an array of n+1 length. Arr [0] is not applicable to us. It was done for the convenience of our understanding.

  • And then at each of the downstream nodes in the binary tree you need to calculate the number of possible flights on the left and right from 1 to I-1 and you can calculate the number of I-nodes.

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

Four,

  • It looks like a binary tree, but don’t let that fool you
  • Remember the three steps of dynamic programming, you can calmly deal with the problem of dynamic return.

Likes, favorites, comments are your points to me