Problem
Given the root of a binary tree, return the values of the nodes visible from the right side, ordered from top to bottom.Example(s)
Consider the following example(s) to understand the expected input and output.Input
root = [1,2,3,null,5,null,4]
1
/ \
2 3
\ \
5 4
Output
[1,3,4] Solution
This solution uses Breadth-First Search (BFS) with a Queue to traverse the tree level by level.For each level, the last node processed is the node visible from the right side, so its value is added to the result.
The children of each node are added to the queue, allowing the next level to be processed in the following iteration.
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
// Add the rightmost node of the current level.
if (i == size - 1) {
result.add(node.val);
}
}
}
return result;
}
Complexity
Each node is added to and removed from the queue exactly once, resulting in a time complexity ofO(n). In the worst case, the queue may contain all nodes at the widest level of the tree, resulting in an extra space complexity of
O(n).