import BinaryTreeRepresentation
from collections import deque

'''
The core idea of this algorithm:
1. Each depth of the tree only select one node.
2. View depth is current size of result list.
'''


# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


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

    def helper(self, curr, result, currDepth):
        if curr is None:
            return

        if currDepth == len(result):
            result.append(curr.val)

        self.helper(curr.right, result, currDepth + 1)
        self.helper(curr.left, result, currDepth + 1)

    def levelOrder2(self, root):
        queue = deque([root])
        res = []
        while queue:
            levelLen = len(queue)
            path = []
            for _ in range(levelLen):
                node = queue.popleft()
                path += node.val,
                if node.left:
                    queue += node.left,
                if node.right:
                    queue += node.right,
            res += path[-1],
        return res


def deserialize(data):
    def doit():
        val = next(vals)
        if val == '#':
            return None
        node = TreeNode(int(val))
        node.left = doit()
        node.right = doit()
        return node
    vals = iter(data.split())
    return doit()


root = deserialize('1 2 # 5 # # 3 # 4 # #')
test = Solution()
print(test.rightSideView(root))
