Binary Tree Right Side View

这题首先明确不可能有O(h）的方法，因为我们不可能保证只走二叉树的一个支路找到所有right side view，原因是因为各种不完全结构的二叉树存在（貌似即使是full tree或者complete tree一样没办法），既然如此，那最容易想到的就是BFS然后拿最后一个点了

class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []

        q = collections.deque([root])
        cur, nxt = 1, 0
        result = []
        tmp = []

        while q:
            node = q.pop()
            tmp.append(node)
            cur -= 1
            if node.right:
                q.appendleft(node.right)
                nxt += 1
            if node.left:
                q.appendleft(node.left)
                nxt += 1
            if not cur:
                result.append(tmp[0].val)
                tmp = []
                cur, nxt = nxt, cur

        return result

还有一种更加优雅的递归方式实现，虽然时间复杂度并没有提高

class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        result = []
        self.helper(root, result, 0)
        return result

    def helper(self, root, res, level):
        if not root:
            return 

        if len(res) == level:
            res.append(root.val)

        self.helper(root.right, res, level + 1)
        self.helper(root.left, res, level + 1)