Count the structurally distinct binary search trees that use every integer from 1 through n exactly once. In a binary search tree, all values in a node's left subtree are smaller than that node, and all values in its right subtree are larger. Trees differ when their left/right child structure differs. Return the number of possible trees.
Example 1:
Input: n = 2
Output: 2Explanation: Either 1 is the root with right child 2, or 2 is the root with left child 1. These are the two distinct structures.
Example 2:
Input: n = 4
Output: 14Explanation: Choosing root 1, 2, 3, or 4 yields respectively 5, 2, 2, and 5 valid structures for the remaining subtrees. Their sum is 14.
Example 3:
Input: n = 1
Output: 1Explanation: The only tree is a single node with value 1.
Constraints:
1 <= n <= 19