511. Right-Leaning Chain
A botanist stores sapling heights in a binary search tree: every key in a node's left subtree is smaller than the node's key, and every key in its right subtree is larger. For a field survey she would rather have the saplings lined up in one row from shortest to tallest, kept as a tree in which no node has a left child and each node's right child holds the next larger key.
Rearrange the tree root into such a chain and return its new root, which holds the smallest key. You may relink the existing nodes. If root is empty, return an empty tree. The chain is compared through its level-order listing, which reads [k1,null,k2,null,k3,...].
Example 1
- Input:
- root = [6,2,9,null,4,7]
- Output:
- [2,null,4,null,6,null,7,null,9]
- Explanation:
The in-order keys are 2, 4, 6, 7, 9, so the chain is 2 -> 4 -> 6 -> 7 -> 9 with every left child empty.
Example 2
- Input:
- root = [8,4,null,2,null,1]
- Output:
- [1,null,2,null,4,null,8]
- Explanation:
A left-leaning path with keys 1, 2, 4, 8 becomes the chain 1 -> 2 -> 4 -> 8 going right.
Constraints
0 ≤ number of nodes ≤ 104
-104 ≤ node key ≤ 104
All keys are distinct and root 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.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)