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.
from collections import deque
def rightSideView(root):
if not root:
return []
result, queue = [], deque([root])
while queue:
level_size = len(queue)
for i in range(level_size):
node = queue.popleft()
if i == level_size - 1:
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return resultFollow-up:
Can you solve this problem using a recursive approach?
