Binary Tree Right Side View
Problem
https://leetcode.com/problems/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.
Example 1:
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Explanation:
Example 2:
Input: root = [1,2,3,4,null,null,null,5]
Output: [1,3,4,5]
Explanation:
Example 3:
Input: root = [1,null,3]
Output: [1,3]
Example 4:
Input: root = []
Output: []
Constraints:
The number of nodes in the tree is in the range
[0, 100].-100 <= Node.val <= 100
Pattern
Tree, Depth-First Search, Breadth-First Search, Binary Tree
Approaches
Code
from __future__ import annotations
from collections import deque
class TreeNode:
"""Node in a binary tree."""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
@classmethod
def from_list(cls, vals: list[int | None]) -> TreeNode | None:
if not vals:
return None
root = cls(vals[0])
queue = deque([root])
children = iter(vals[1:])
while queue:
node = queue.popleft()
for side in ("left", "right"):
val = next(children, None)
if val is not None:
child = cls(val)
setattr(node, side, child)
queue.append(child)
return root
def to_list(self) -> list:
result = []
queue = [self]
while queue:
node = queue.pop(0)
if node:
result.append(node.val)
queue.append(node.left)
queue.append(node.right)
else:
result.append(None)
while result and result[-1] is None:
result.pop()
return result
def rightSideView(root: TreeNode | None) -> list[int]:
if root is None:
return []
view = []
queue = deque([(root, 0)])
while queue:
node, level = queue.popleft()
if node.left:
queue.append((node.left, level + 1))
if node.right:
queue.append((node.right, level + 1))
if len(queue) == 0 or level < queue[0][1]:
view.append(node.val)
return view
Test
>>> from binary_tree_right_side_view__bfs import rightSideView, TreeNode
>>> rightSideView(TreeNode.from_list([1, 2, 3, None, 5, None, 4]))
[1, 3, 4]
>>> rightSideView(TreeNode.from_list([1, None, 3]))
[1, 3]
>>> rightSideView(None)
[]