<div>
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:
<pre>Input: root = [1,2,3,null,5,null,4] Output: [1,3,4] </pre>
Example 2:
<pre>Input: root = [1,null,3] Output: [1,3] </pre>
Example 3:
<pre>Input: root = [] Output: [] </pre>
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
</div>
题目大意：
二叉树从右看的节点列表。
解题思路：
BFS按层访问的最后一个
解题步骤：
N/A
注意事项：
- 需要知道最后一个，所以引入i，不能用enumerate，只能用len
- deque([root])不是deque(root)
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17def 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)
