A leaflet courier covers a branching road network shaped like a binary tree. She hands out a leaflet at a junction the moment she first reaches it, then handles its two branches one after the other, finishing one branch completely before starting the other. Her rule: at every junction she takes the branch with more junctions in it first. If both branches have the same number of junctions, she takes the left one first. A missing branch has 0 junctions.
Return the node values in the order she hands out leaflets ([] for an empty tree).
Examples
1
/ \
2 3
/ / \
4 5 6
/
7
Input: root = build_tree([1, 2, 3, 4, None, 5, 6, None, None, None, None, 7])
Output: [1, 3, 6, 7, 5, 2, 4]
Explanation: 3's branch has 4 junctions and 2's has 2; under 3, 6's branch (2) beats 5's (1).
Input: root = build_tree([8, 9, 4, None, None, 2, 7])
Output: [8, 4, 2, 7, 9]
Explanation: 2 and 7 tie, so the left one goes first.
Constraints
0 <= number of nodes <= 10**5; the depth can be close to the number of nodes.-10**9 <= node.val <= 10**9; values may repeat.- Target complexity: O(n).
Goals
- Compute every subtree size bottom-up without recursion
- Run a preorder whose child order depends on those sizes
- Keep the whole job linear on trees 10**5 levels deep