LeetCode-096 - Different Binary Search Trees Different Binary Search Tree Solutions 1: Recursive Solutions 1: Regularity

Title Description: Give you an integer n, find exactly n nodes and node values are not the same from 1 to n How many kinds of binary search trees? Returns the number of species of binary search tree that satisfies the meaning of the topic. Binary search tree: Also known as a binary sort tree, it is either an empty tree or a binary tree with the following properties: if its left subtree is not empty, the values of all nodes on the left subtree are less than the values of its root node; if its right subtree is not empty, the values of all nodes on the right subtree are greater than the values of its root node; its left and right subtrees are also binary sort trees. For an example, see the leetcode website. Source: Leetcode Links: https://leetcode-cn.com/problems/unique-binary-search-trees/ The copyright belongs to the link network. For commercial reprints, please contact the official authorization, non-commercial reprints please indicate the source.

First, when n is 0, the result is an empty tree, returning an empty list directly. When n is greater than 0, the recursive method is used to obtain the left and right subtrees separately, and the recursion process is as follows:

All nodes can be used as root nodes, that is, all values from 1 to n are traversed as root nodes, and the current root node is i;

Then all the values on the left side of i are recursively called methods as the left subtree of i;

All values to the right of i are recursively called methods as the right subtree of i;

Finally, the root node i and the corresponding left and right subtrees are put together into a tree and put into the result set.

Finally, the size value of the returned result set is the number of species of the binary search tree that meet the criteria. Description: This method refers to leetcode-095- a different binary search tree ii, but timed out on submission.

Looking for the regularity shows that when the integer is n, the result of the binary search number is the sum of all the previous possible results.

【Daily Message】 Youth is the cost, but it is not worth it if you don't work hard.