Clockwise Border of Binary Tree
Given a binary tree, return its border nodes in clockwise order. The clockwise border starts with the root, then visits the right border from top to bottom, then all leaf nodes from right to left, and finally the left border from bottom to top.
A node must appear only once in the answer. If a border node is also a leaf, include it only as a leaf.
If the tree has only one node, return only the root value.
Class
Binary Tree Border
BinaryTreeBorder()
- Creates an object that can compute the clockwise border of a binary tree.
Methods
Clockwise Border
List<Integer> clockwiseBorder(List<String> tree)
- Returns the border nodes of the binary tree in clockwise order.
- Each string in
tree represents one node in the format "value,leftIndex,rightIndex".
value is the integer value of the node.leftIndex is the index of the left child in tree, or -1 if there is no left child.rightIndex is the index of the right child in tree, or -1 if there is no right child.- The root of the tree is always at index
0.
- The output must be deterministic.
- The right border starts from the root's right child. If the root has no right child, the right border is empty.
- While following the right border, prefer the right child. If the right child is missing, move to the left child.
- The left border starts from the root's left child. If the root has no left child, the left border is empty.
- While following the left border, prefer the left child. If the left child is missing, move to the right child.
- Distinct nodes with the same value should still be included separately if both are on the border.
Clockwise Border Order
- Add the root node first.
- Add the right border from top to bottom, excluding leaf nodes.
- Add all leaf nodes from right to left by visiting the right child before the left child.
- Add the left border from bottom to top, excluding leaf nodes.
- Do not add the same node more than once.
Constraints
1 ≤ tree.size() ≤ 100,000-1,000,000,000 ≤ value ≤ 1,000,000,000-1 ≤ leftIndex < tree.size()-1 ≤ rightIndex < tree.size()leftIndex ≠ rightIndex for every node where both children exist.- The input always represents a valid binary tree rooted at index
0.
- The tree does not contain cycles.
Examples
Example 1
clockwiseBorder(tree = ["10,1,2", "5,3,4", "20,-1,5", "3,-1,-1", "7,-1,-1", "30,-1,-1"])
Output: [10,20,30,7,3,5]
Explanation: The clockwise border is root 10, right border 20, leaves from right to left 30,7,3, and left border bottom to top 5.
Example 2
clockwiseBorder(tree = ["1,1,-1", "2,2,-1", "3,3,-1", "4,-1,-1"])
Output: [1,4,3,2]
Explanation: The tree has only a left chain. The right border is empty, the leaf 4 is added, and the remaining left border is added from bottom to top.
Example 3
clockwiseBorder(tree = ["8,-1,1", "12,-1,2", "16,-1,3", "20,-1,-1"])
Output: [8,12,16,20]
Explanation: The tree has only a right chain. The left border is empty, and the clockwise border is the same as visiting the chain from root to leaf.
Example 4
clockwiseBorder(tree = ["42,-1,-1"])
Output: [42]
Explanation: The tree has only one node, so only the root value is returned.