Simple level-order traversal, Python, O(n)


  • 0
    S

    The key is that we should choose a specific delimiter for each level such that when we finish visiting each level, the last node of each level is viewed.

    from collections import deque
    class Solution(object):
        def rightSideView(self, root):
            """
            :type root: TreeNode
            :rtype: List[int]
            """
            # level order traversal, and we can see the right-most node for each level
            if root is None:
                return []
            q = deque([root, None]) # None is the delimiter for a level
            view = []
            pre = None  # the previous node we have just visited
            while q:
                node = q.popleft()
                if node is None:
                    view.append(pre.val)
                    if not q:   # q is empty now
                        return view
                    q.append(None)  # a new level delimiter
                else:
                    if node.left is not None:
                        q.append(node.left)
                    if node.right is not None:
                        q.append(node.right)
                    pre = node
            return view

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.