動機

複習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