A sorted catalogue arrives as a singly linked list of strictly increasing integers (ListNode with val and next). Build a height-balanced binary search tree containing exactly those values and return its root. Height-balanced means that at every node the heights of the two subtrees differ by at most 1. Any balanced tree with the right values is accepted.
Examples
Input: head = list_to_linked([1, 3, 4, 7, 9]) 1 -> 3 -> 4 -> 7 -> 9
Output (one valid answer):
4
/ \
1 7
\ \
3 9
tree_to_list(...) == [4, 1, 7, None, 3, None, 9]
Constraints
0 <= length of the list <= 2000- Values are strictly increasing
- The result's inorder traversal must equal the list, and it must be height-balanced
Goals
- Build a height-balanced tree whose inorder order matches the chain
- Consume a linked list in order without random access