Back to Trees
Medium
Binary Tree Right Side View
Given the `root` of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Examples
Input:root = [1,2,3,null,5,null,4]
Output:[1,3,4]
Input:root = [1,null,3]
Output:[1,3]
Input:root = []
Output:[]
Constraints
The number of nodes in the tree is in the range [0, 100].-100 <= Node.val <= 100
Approach
Use BFS for level order traversal. Since we are looking from the right side, at each level we only want to collect the very last node processed. Get the number of nodes at the current level, iterate through them, and if it's the last iteration for that level (i.e., `i == levelSize - 1`), append the node's value to the result list.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
The space complexity is determined by the maximum number of nodes at any level (queue size), which is at most n/2.
Solution.java
class Solution { public List<Integer> rightSideView(TreeNode root) { List<Integer> res = new ArrayList<>(); if (root == null) return res; Queue<TreeNode> q = new LinkedList<>(); q.offer(root); while (!q.isEmpty()) { int levelSize = q.size(); for (int i = 0; i < levelSize; i++) { TreeNode node = q.poll(); // If it's the last node in this level if (i == levelSize - 1) { res.add(node.val); } if (node.left != null) q.offer(node.left); if (node.right != null) q.offer(node.right); } } return res; }}