動機
複習bfs
Problem
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
Sol
bfs看每一level的最後一個
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
if not root:
return []
ret,q = [], deque([[root]])
while q:
rs = q.popleft()
ret.append(rs[-1].val)
rs = sum([[x for x in [r.left, r.right] if x] for r in rs if r],[])
if rs:
q.append(rs)
return ret