AI题库 · GESP-Python六级题库
题目分享 #16708
给定一棵二叉树,采用广度优先搜索(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))
A
(1)depth , depth ;(2)0 , max_depth
B
(1)depth + 1 , depth + 1 ;(2)0 , max_depth + 1
C
(1)depth + 1 , depth + 1 ;(2)1 , max_depth + 1
D
(1)depth , depth ;(2)1 , max_depth
AI题库 · 编程考级与信奥赛真题库
查看答案 →
复制链接后可在微信、QQ、小红书等平台粘贴分享;答案与解析在题目页。