https://leetcode.com/problems/binary-tree-right-side-view/

还是比较简单的,考察遍历。可以用 DFS 或 BFS

DFS 用什么遍历都可以,最后都会被最右边的覆盖。

BFS 在每一层结束的时候将最后一个元素加进答案。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        """
        Level order traversal
        """
        if not root:
            return []
        q = [root]

        count = len(q)
        res = []
        while q:
            n = q.pop(0)
            if n.left: q.append(n.left)
            if n.right: q.append(n.right)
            count -= 1
            if count == 0:
                res.append(n.val)
                count = len(q)

        return res

        """
        pre-order
        """
        if not root:
            return []

        res = []
        def helper(n, level):
            if not n: return
            if level >= len(res):
                res.append(n.val)
            else: res[level] = n.val
            helper(n.left, level + 1)
            helper(n.right, level + 1)
        helper(root, 0)

        return res