给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
depth_mapping_rightmost_value = dict() # 深度为索引,存放节点的值
max_depth = -1
queue = deque([(root, 0)])
while queue:
node, depth = queue.popleft()
if node is not None:
# 维护二叉树的最大深度
max_depth = max(max_depth, depth)
""" 如果每层存放节点都是从左往右,那么每一层最后一个访问到的节点值是每层最右端节点,因此不断更新对应深度的信息即可"""
depth_mapping_rightmost_value[depth] = node.val
queue.append((node.left, depth + 1))
queue.append((node.right, depth + 1))
return [depth_mapping_rightmost_value[depth] for depth in range(max_depth + 1)]