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

    def __repr__(self):
        return "{}".format(self.val)


class Solution:
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        Time: N
        Space: N
        """
        if not root:
            return list()
        result, current = [], [root]
        counter = 0
        while current:
            counter += 1
            next_level, vals = [], []
            for node in current:
                if node:
                    vals.append(node.val)
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)
            if counter % 2:
                result.append(vals)
            else:
                result.append(list(reversed(vals)))
            current = next_level
        return result


if __name__ == "__main__":
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.right.left = TreeNode(4)
    root.right.right = TreeNode(5)
    print(Solution().zigzagLevelOrder(root))
