Leetcode 103. Binary Tree Zigzag Level Order Traversal

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

We can solve the problem easily based on last problem: just reverse the odd level. We can reverse it in process or in result.

Solution:

# T:O(n) S:O(n)
class Solution:
    # @param root, a tree node
    # @return a list of lists of integers
    def preorder(self, root, level, res):
        if root:
            if len(res) < level+1: res.append([])
            if level % 2 != 0:
                res[level].insert(0, root.val)
            else:
                res[level].append(root.val)
            self.preorder(root.left, level+1, res)
            self.preorder(root.right, level+1, res)
    def zigzagLevelOrder(self, root):
        res=[]
        self.preorder(root, 0, res)
        return res

Run Time: 76 ms