523. Sorted Chain to Search Tree
A conveyor belt carries parcels whose ticket numbers appear in strictly increasing order, stored as a singly linked list starting at head. The warehouse wants to turn this belt into a balanced search tree for fast lookups.
Build the tree with this exact rule so the answer is unique: for a run of m consecutive tickets, the root is the ticket at 0-based position m / 2 (integer division) of that run; the tickets before it form the left subtree and the tickets after it form the right subtree, built by the same rule. Return the root. An empty list gives an empty tree.
Example 1
- Input:
- head = [-4,0,3,8,11]
- Output:
- [3,0,11,-4,null,8]
- Explanation:
Five values: position 5/2 = 2 gives the root 3; the left run [-4, 0] has root 0 (position 1) with left child -4; the right run [8, 11] has root 11 with left child 8.
Example 2
- Input:
- head = [2,5,6,9]
- Output:
- [6,5,9,2]
- Explanation:
Four values: the root is position 2, i.e. 6; the left run [2, 5] has root 5 with left child 2, and the right run [9] is a single node.
Constraints
0 ≤ length of list ≤ 2 * 104
-105 ≤ value ≤ 105
Values are strictly increasing from head to tail
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)