1601. Tree Into Two-Way Chain
A library indexes its books in a binary search tree whose keys are all distinct. Given the root, walk the tree in in-order (left subtree, node, right subtree) and link the visited keys into a new doubly linked list: each list node holds one key, its next points to the following key in the walk and its prev points to the previous one. The first node has prev equal to null and the last node has next equal to null, so the list is not circular.
Return the head of the list, or null when the tree is empty. Because a search tree is traversed in increasing key order, the list comes out sorted. Run in O(n) time; an explicit stack is recommended so a degenerate tree cannot overflow the call stack.
Example 1
- Input:
- root = [4,2,6,1,3,5,7]
- Output:
- [1,2,3,4,5,6,7]
- Explanation:
The in-order walk visits 1, 2, 3, 4, 5, 6, 7, which become the list in that order.
Example 2
- Input:
- root = [10,5,null,2]
- Output:
- [2,5,10]
- Explanation:
The tree leans left; in-order gives 2, 5, 10.
Constraints
0 ≤ nodes ≤ 1000; keys are distinct integers; the tree is a valid binary search tree.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(h)