Binary Tree Right Side View
Given the root of a binary tree, return the rightmost node value in the nth level, where the root is at level 1 and the rightmost node is at level 1.
Constraints:
- The number of nodes in the tree is in the range [1, 100].
- 1 <= Node.val <= 100
Examples:
Input: [1,2,3,null,5,null,4]
Output: [1,3,4]
Explanation: The rightmost node values in each level are 1, 3, and 4.
Solutions
Breadth-First Search (BFS)
Time: O(N)Space: O(N)
We use a queue to perform a level-order traversal of the binary tree. In each level, we add the rightmost node's value to the result list.
import java.util.Queue;
import java.util.LinkedList;
public
class Solution {
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 levelSize = queue.size();
for (int i = 0;
i < levelSize;
i++) {
TreeNode node = queue.poll();
if (i == levelSize - 1) result.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return result;
}
}Follow-up:
Can you solve this problem using a recursive approach?
