498. Outline of the Tree
A cartographer wants to trace the silhouette of a binary tree whose top node is root, walking around it anticlockwise. Return the values met on the walk, in this order: first the root; then the left boundary from the root's left child downward, always taking the left child when it exists and otherwise the right child, but leaving out leaves; then all the leaves from left to right; and finally the right boundary, built the same way (right child preferred), leaving out leaves and the root, listed from the bottom up.
No node appears twice. A tree with a single node returns just that value, and an empty tree returns an empty array.
Example 1
- Input:
- root = [14,6,18,3,9,15,21,null,null,7]
- Output:
- [14,6,3,7,15,21,18]
- Explanation:
Root 14, left edge 6, leaves 3, 7, 15, 21 from left to right, then the right edge 18.
Example 2
- Input:
- root = [10,5,12,null,8,null,20,3,9]
- Output:
- [10,5,8,3,9,20,12]
- Explanation:
Root 10, left edge 5 then 8 (right child used since 5 has no left child), leaves 3, 9, 20, then right edge 12.
Constraints
0 ≤ number of nodes ≤ 105
-1000 ≤ Node.val ≤ 1000, values may repeat.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)