A branching irrigation network forms a binary tree of valves with distinct integer labels.
A drone photographed it and listed the valves row by row, top to bottom and left to right
within each row (the level order, rows). A ground crew walked it and listed the valves in
inorder (left part, valve, right part), giving walk.
Rebuild the network and return its root (None if both lists are empty). The two lists always
come from one binary tree, and they determine it uniquely.
Examples
8
/ \
4 9
\ \
6 2
/
5
Input: rows = [8, 4, 9, 6, 2, 5], walk = [4, 5, 6, 8, 9, 2]
Output: tree_to_list(root) == [8, 4, 9, None, 6, None, 2, 5]
Input: rows = [], walk = []
Output: tree_to_list(root) == []
Constraints
0 <= len(rows) == len(walk) <= 10**5; both hold the same distinct labels.- The tree can be as deep as it has nodes (a long chain), so a recursive rebuild may run out of stack.
- Target complexity: O(n).
Goals
- Rebuild a binary tree from its level order and its inorder
- Use inorder index ranges to decide whether a child exists
- Build trees of depth 10**5 without recursion