手写二叉树的右视图,为什么不能只沿右子树走?
右视图取每一层最右侧的节点。用队列按层遍历,每层按从左到右的顺序入队,记录该层最后出队的节点即可。
不能只沿右孩子走:根的右子树可能较浅,更深一层能看到的节点可能来自左子树。例如,根的左孩子是 2、右孩子是 3,只有 2 还有左孩子 4,右视图是 [1, 3, 4]。
from collections import deque
def right_side_view(root): if root is None: return [] queue = deque([root]) result = [] while queue: width = len(queue) for i in range(width): node = queue.popleft() if node.left is not None: queue.append(node.left) if node.right is not None: queue.append(node.right) if i == width - 1: result.append(node.val) return result每层开始时先保存节点数,避免把下一层也处理进去。共访问 n 个节点,时间 O(n);队列空间 O(w),w 是最大层宽,不含返回结果。
资料
LeetCode 199 题面与边界。代码为本站编写。