947. Convert BST to Sorted Doubly Linked List

Given the root of a binary search tree, convert it in place to a sorted circular doubly linked list, where left acts as the previous pointer and right as the next pointer. Return the sequence of values in the list order (ascending), which is the BST's inorder traversal, as an array. The tree is given as a level-order BST array.

Input: A level-order BST array.

Output: Array — the values in doubly-linked-list (ascending) order.

Examples

Input: [4,2,5,1,3]
Output: [1,2,3,4,5]
Explanation: Inorder gives the sorted DLL order.

Input: [5]
Output: [5]
Explanation: Single node.

Input: []
Output: []
Explanation: Empty tree.

Constraints

• 0<=nodes<=2000
• valid BST

Asked by