DiffPush Tier Binary Trees · Hard O(n) · O(1)
An inventory drone must list every shelf of a tree-layout aisle in left-to-right order while forbidden from carrying a routing table. Its trick: whenever it steps into a left branch, it first strings a temporary return-thread from that branch's rightmost shelf up to the current junction. The thread tells it when the branch is exhausted; it snips the thread on the way out, restoring the aisle byte for byte.
Input: A binary tree as a level-order array (null marks a missing child).
Output: Return the node values in inorder (left subtree, root, 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: [4,2,5,1,3,6]
The left wing reads 4-2-5, then the root 1, then 3 with its right child 6.
Input: {"tree":[1,null,2,3]}
Output: [1,3,2]
The root has no left subtree, so 1 leads; node 2's left child 3 precedes it.