Construct Every BST Shape on Consecutive Keys

### Problem Construct every structurally distinct binary search tree containing exactly the keys 1 through `n`, each once. Return the tree roots in any order. In each BST, every left-subtree key is smaller than its root key and every right-subtree key is larger. The supplied `TreeNode` has `val`, `left`, and `right` fields. Preserve the original root-pointer collection interface: ```cpp vector<TreeNode*> generateTrees(int n); ``` ### Example ```text Input: n = 2 One valid output, displayed in level-order notation: [[2,1],[1,null,2]] ``` These displays represent two returned tree roots: one has root 2 with left child 1, and the other has root 1 with right child 2. They are not a replacement array-based API. ### Constraints & Assumptions - `1 <= n <= 8`. - Each returned tree contains all `n` keys exactly once and satisfies the BST ordering. - Include every structural possibility once; only the order of the returned roots is free. ### Clarifying Questions to Ask - Is only the number of trees needed? No; return their roots. - Do different root choices count separately? Yes, when they produce different tree structures. ```hint Preserve what is being enumerated The result consists of complete trees with the specified keys, rather than traversal arrays or just a count. ``` ### What a Strong Answer Covers - Complete structural enumeration without duplicate trees. - Correct key placement for every generated structure. - Ownership of constructed nodes and output-sensitive costs. ### Follow-up Questions - What is the result for `n=1`? - How can two correct collections of tree roots be compared without imposing an order?