DiffPush Tier Binary Trees · Hard O(n) · O(1)
A night inspector must verify every bay of a tree-shaped storage aisle and is under a strict rule: carry nothing — no clipboard stack, no breadcrumbs. Her trick is temporary chalk arrows: before descending into a branch she chalks the exit thread from its last bay back up to the current junction, erases the chalk on the way back, and leaves the aisle exactly as she found it, all bays visited hub-first.
Input: A binary tree as a level-order array (null marks a missing child).
Output: Return the node values in preorder (root, left subtree, right subtree).
1 <= number of nodes <= 10^5-10^4 <= node value <= 10^4Expected extra space: O(1) — Morris threading, no stack or queueInput: {"tree":[1,2,3,4,5,null,6]}
Output: [1,2,4,5,3,6]
Root first, then the whole left wing 2-4-5, then 3 and its lone child 6.
Input: {"tree":[1,null,2,3]}
Output: [1,2,3]
No left child at the root, so the walk drops straight down the right spine.