Shulou(Shulou.com)05/31 Report--

This article editor for you to introduce in detail the "python binary search tree case analysis", the content is detailed, the steps are clear, the details are handled properly, I hope this "python binary search tree case analysis" article can help you solve your doubts, following the editor's ideas slowly in-depth, together to learn new knowledge.

[title]

Given an integer n, find 1. How many binary search trees are there with n nodes?

Example:

Enter: 3

Output: 5

Explanation:

Given n = 3, a binary search tree with five different structures:

1 3 3 2 1

\ /\\

3 2 1 1 3 2

/ /\

2 1 2 3

[ideas]

For a tree with n nodes, except for the root node, the number distribution of nodes on the left subtree and the right subtree may be left 0, right nMul 1, left 1, right nMel 2, right 1, left nMel 2, right 0.

Expressed by formula: DP [n] = dp [0] * dp [n-1] + dp [1] * dp [n-2] + + dp [n-2] * dp [1] + dp [n-1] * dp [0]

[code]

Python version

Class Solution:

Def numTrees (self, n: int)-> int:

If n < 2:

Return n

Dp = [0] * (n + 1)

Dp [0], dp [1] = 1,1

# dp [I] = dp [0] * dp [I-1] + dp [1] * dp [I-2] +. + dp [I-1] * dp [0]

For i in range (2, n + 1):

For j in range (I):

Dp [I] + = dp [j] * dp [I-j-1]

Print (dp)

Return dp [- 1] has read this article, "python binary search tree example analysis" article has been introduced, want to grasp the knowledge of this article still need to do your own practice to understand, if you want to know more related articles, welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.