Walk around the outside of a binary tree anticlockwise, starting at the root, and list the values you pass. The walk consists of three parts:
- the left edge: starting at the root's left child, keep going down, taking the left child when it exists and the right child otherwise, and stop before reaching a leaf;
- all leaves from left to right;
- the right edge: the same as the left edge but starting at the root's right child, preferring the right child, listed bottom-up.
The root is listed first and only once. No node appears twice. Return [] for an empty tree.
Examples
1
/ \
2 3
/ \ \
4 5 6
/ \
7 8
Input: root = build_tree([1, 2, 3, 4, 5, None, 6, None, None, 7, 8])
Output: [1, 2, 4, 7, 8, 6, 3]
Explanation: root 1; left edge [2] (4 is a leaf); leaves [4, 7, 8, 6]; right edge [3] (6 is a leaf).
Input: root = build_tree([1, None, 2, None, 3])
Output: [1, 3, 2]
Explanation: no left edge; the only leaf is 3; the right edge is [2], read bottom-up.
Constraints
0 <= number of nodes <= 2000-10**4 <= node.val <= 10**4- Target complexity: O(n) time.
Goals
- Split the boundary into left edge, leaves and right edge
- Follow an edge by preferring the outer child
- Avoid listing the root or a leaf twice