# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:

        if not root:

            return []

        stack = [root]

        ans = []

        while stack:

            tem_stack=[]

            tem_ans = []

            for i in stack:

                tem_ans.append(i.val)

                if i.left:

                    tem_stack.append(i.left)

                if i.right:

                    tem_stack.append(i.right)

            stack = tem_stack

            ans.append(tem_ans)

        for i in range(len(ans)):

            if i%2!=0:

                ans[i] = ans[i][::-1]

        return ans

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:

        if not root:

            return []

        stack = [root]

        ans = []

        depth = 0

        while stack:

            tem_ans,tem_stack = [],[]

            for i in stack:

                tem_ans.append(i.val)

                if i.left:

                    tem_stack.append(i.left)

                if i.right:

                    tem_stack.append(i.right)

            if depth%2 == 0:

                ans.append(tem_ans)

            else:

                ans.append(tem_ans[::-1])

            stack = tem_stack

            depth += 1

        return ans

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:

        res = []

        def helper(root, depth):

            if not root: return

            if len(res) == depth:

                res.append([])

            if depth % 2 == 0:

                res[depth].append(root.val)

            else:

                res[depth].insert(0, root.val)

            helper(root.left, depth + 1)

            helper(root.right, depth + 1)

        helper(root, 0)

        return res