LeetCode_ 96_ Different binary search trees

Topic link

• https://leetcode.cn/problems/unique-binary-search-trees/

Title Description

Give you an integer n , Seek just by n Composed of nodes with node values from 1 To n Different from each other Binary search tree How many kinds? ？ Returns the number of binary search trees satisfying the meaning of the question .

Example 1：

 Input ：n = 3
 Output ：5

Example 2：

 Input ：n = 1
 Output ：1

Tips ：

• 1 <= n <= 19

Their thinking

Dynamic programming

First, clarify the definition of binary search tree ： It could be an empty tree , Or a binary tree that has the following properties ： If its left subtree is not empty , Then the value of all nodes in the left subtree is less than the value of its root node ; If its right subtree is not empty , Then the value of all nodes in the right subtree is greater than the value of its root node ; Its left 、 The right subtree is also a binary sort tree .

By way of example 1 As an example ,dp[3] Is to use elements 1 Number of binary search trees for the root node + Elements 2 Is the number of root nodes + Elements 3 Is the number of root nodes . And according to the definition of binary search tree , It can be summarized as follows ：

• 1 Is the number of root nodes = Zuo Zi Shu you 0 Number of elements * Right subtree has 2 Number of elements
• 2 Is the number of root nodes = Zuo Zi Shu you 1 Number of elements * Right subtree has 1 Number of elements
• 3 Is the number of root nodes = Zuo Zi Shu you 2 Number of elements * Right subtree has 0 Number of elements
• a key ： Yes 2 The number of elements is dp[2], Yes 1 The number of elements is dp[1]

So it can be concluded that dp[3] = dp[0] * dp[2] + dp[1] * dp[1] + dp[2] * dp[0], To sum up, we can get

dp[i] += dp[j-1] * dp[i-j]

among j Equivalent to the root node , from 1 Traversing i until .j-1 by j Is the number of left subtree nodes of the root node ,i-j Is the number of nodes in the right subtree

AC Code

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