单选题 适中
#16708

给定一棵二叉树,采用广度优先搜索(BFS) 算法,返回右视图所有节点的值。其中右视图定义为:二叉树的右视图是从树的右侧看过去时可见的节点集合,即右视图中的每个节…

给定一棵二叉树,采用广度优先搜索(BFS) 算法,返回右视图所有节点的值。其中右视图定义为:二叉树的右视图是从树的右侧看过去时可见的节点集合,即右视图中的每个节点都是某一层中最右侧的节点。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def rightSideView(root):
    rightmost_value_at_depth = {}
    max_depth = -1

    node_queue = []
    depth_queue = []
    node_queue.append(root)
    depth_queue.append(0)

    while node_queue:
        node = node_queue.pop(0)
        depth = depth_queue.pop(0)

        if node is not None:
            max_depth = max(max_depth, depth)
            rightmost_value_at_depth[depth] = node.val

            node_queue.append(node.left)
            node_queue.append(node.right)

            # (1) 填空处
            depth_queue.append(depth + 1)
            depth_queue.append(depth + 1)

    right_view = []
    # (2) 填空处
    for depth in range(max_depth + 1):
        right_view.append(rightmost_value_at_depth[depth])

    return right_view

if __name__ == "__main__":
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.right = TreeNode(5)
    root.right.right = TreeNode(4)

    print(rightSideView(root))


未登录也能判分,登录后才会记录
答案与解析
正确答案:B
解析
使用BFS遍历二叉树,按层处理节点。每层维护一个映射记录该层最后访问的节点值,因队列中同一层节点按从左到右入队,同层后续节点会覆盖前序节点值,最终保留最右侧节点。节点入队时将其左右子节点依次加入队列,对应深度加1。初始化根节点深度为0,故遍历所有层需从0开始到max_depth(含)。遍历完成后,按深度从小到大收集每层最右节点值形成右视图结果序列。