自助网站建设程序,网络域名费用多少钱,个人服务器 网站建设,济南市建设工程招标网官网描述
给定一个二叉树的 根节点 root#xff0c;想象自己站在它的右侧#xff0c;按照从顶部到底部的顺序#xff0c;返回从右侧所能看到的节点值。
思路
对树进行深度优先搜索#xff0c;在搜索过程中#xff0c;我们总是先访问右子树。那么对于每一层来说#xff0c;…描述
给定一个二叉树的 根节点 root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。
思路
对树进行深度优先搜索在搜索过程中我们总是先访问右子树。那么对于每一层来说我们在这层见到的第一个结点一定是最右边的结点但凡循环or遍历都会有中间状态产生如奇偶、遍历的计数、嵌套遍历的话内层循环就会有首位值这些都将是重要信号可以暂存利用
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# 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 -1queue 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.valqueue.append((node.left, depth 1))queue.append((node.right, depth 1))return [depth_mapping_rightmost_value[depth] for depth in range(max_depth 1)]
