LeetCode 199 Binary Tree Right Side View

LeetCode

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

Example 2:

Input: root = [1,null,3]
Output: [1,3]

Example 3:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 100]. -100 <= Node.val <= 100

题目大意：

二叉树从右看的节点列表。

解题思路：

BFS按层访问的最后一个

解题步骤：

N/A

注意事项：

1. 需要知道最后一个，所以引入i，不能用enumerate，只能用len
2. deque([root])不是deque(root)

Python代码：

def rightSideView(self, root: TreeNode) -> List[int]:
	if not root:
		return []
	res = []
	queue = collections.deque([root])
	while queue:
		i, len_q = 0, len(queue) # remember
		for _ in range(len_q):
			node = queue.popleft()
			if i == len_q - 1:
				res.append(node.val)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
			i += 1
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(n)