How Far Have You Gotten in Leet — (4)

Description

Explanation

1. BST has two leaves on every single level, in which the left side is always smaller and the right bigger than its root node.
2. When N is k, the value of the root node could be 1 to k and one or more numbers on each side make diverse sub-trees.
3. The number of trees of a root node is multiplying the number of sub-trees on the left and on the right.
4. Getting a total combination of n is to sum up all the number of trees created in each root node.

Solution

Review

Afraid of the BST. Thought that it was a sort of a combination of graph and DP, which felt so hard at first. Once I figured out the rule of BST, it did not take long to find the way to get the number of trees. One reminder: DP is to memorize each step’s result that comes out according to a general rule.