Mid/Senior
Boundary of Binary Tree
Given the root of a binary tree, return the values of its boundary in anti-clockwise order.
The boundary includes, in order:
- The
rootnode. - The left boundary, excluding leaf nodes.
- All leaf nodes from left to right.
- The right boundary, excluding leaf nodes, in reverse order.
Definitions:
- A leaf is a node with no children.
- The left boundary is the path from
root.leftdown to the leftmost node, choosing the left child when possible; if a node has no left child, choose its right child instead. - The right boundary is the path from
root.rightdown to the rightmost node, choosing the right child when possible; if a node has no right child, choose its left child instead.
Do not include any node more than once in the returned boundary.
Example 1
1
\
2
/ \
3 4Input
root = [1,null,2,3,4]Output
[1,3,4,2]The root is 1, there is no left boundary, the leaves are 3 and 4, and the right boundary contributes 2 at the end.
Example 2
1
/ \
2 3
/ \ /
4 5 6
/ \ / \
7 8 9 10Input
root = [1,2,3,4,5,6,null,null,null,7,8,9,10]Output
[1,2,4,7,8,9,10,6,3]The boundary is root 1, left boundary 2, leaves 4, 7, 8, 9, 10, then the reversed right boundary 6 and 3.
Constraints
- 1 <= number of nodes <= 10^4
- -1000 <= Node.val <= 1000