At Meta, you may need to transform ordered tree-based data into a sequential structure for efficient traversal. Given the root of a binary search tree (BST), convert it in-place into a sorted doubly linked list using the tree nodes themselves.
The doubly linked list must use the BST's left pointer as prev and right pointer as next. Return the head of the list. The resulting list should be sorted in ascending order. Do not create new nodes.
root, the root node of a BST, or nullleft and right pointers as prev and nextExample 1
Input: root = [4,2,5,1,3]
Output: [1,2,3,4,5]
Explanation: An in-order traversal of the BST yields sorted order, and the nodes are linked in that order.
Example 2
Input: root = [2,1,3]
Output: [1,2,3]
Explanation: Node 1 becomes the head, 2 is in the middle, and 3 is the tail.
0 <= number of nodes <= 10^5-10^9 <= node.val <= 10^9