给定一棵二叉树,采用广度优先搜索(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_queue.append(__________)
right_view = []
# (2) 补全
for depth in range(____________):
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))