Return the roots of all structurally distinct binary search trees that contain each value from 1 through n exactly once.
In a binary search tree, every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger. Trees with different left/right arrangements are distinct.
Return every valid tree exactly once, in any order. The examples show each tree in level order, using null for missing children and omitting trailing nulls.
Example 1:
Input: n = 1
Output: [[1]]Explanation: With only value 1, the only valid tree is a single node.
Example 2:
Input: n = 2
Output: [
[1,null,2],
[2,1]
]Explanation: Either value can be the root. Root 1 must have right child 2; root 2 must have left child 1. These are the only two structures.
Example 3:
Input: n = 3
Output: [
[1,null,2,null,3],
[1,null,3,2],
[2,1,3],
[3,1,null,null,2],
[3,2,null,1]
]Explanation: Root 1 permits two arrangements of values 2 and 3 on its right. Root 2 has left child 1 and right child 3. Root 3 permits two arrangements on its left, giving five distinct trees.
Constraints:
1 <= n <= 8