Leetcode 199. Binary Tree Right Side View

# TimeComplexity = O(n)
# 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]:
        # 1st solution
#         if not root: return []
            
#         right = self.rightSideView(root.right)
#         left = self.rightSideView(root.left)
#         return [root.val] + right + left[len(right):]
        
    # 2nd solution
        if not root: return []
        
        q = collections.deque([root, None])
        right = False
        res = [root.val]
        
        while q:
            node = q.popleft()
            
            if node is None:
                if q: q.append(None)
                right = False
            else:
                if node.right:
                    q.append(node.right)
                    if right is False:
                        res.append(node.right.val)
                        right = True
                
                if node.left: 
                    q.append(node.left)
                    if not node.right and right is False:
                        res.append(node.left.val)
                        right = True
        return res
                    

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