Binary Tree Zigzag Level Order Traversal

Quesion

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

Have you met this question in a real interview? Yes Example Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

思路

levelOrder加一个变量level, level为奇数时一样，level为偶数时，将该层的list reverse

Soltuion

class Solution:
    """
    @param root: The root of binary tree.
    @return: A list of list of integer include 
             the zig zag level order traversal of its nodes' values
    """
    def zigzagLevelOrder(self, root):
        # write your code here
        if not root:
            return []
        queue = deque()
        queue.append(root)
        level = 1
        currentLevelNum = 1
        nextLevelNum = 0
        resultList = []
        levelList = []
        while queue:
            node = queue.popleft()
            levelList.append(node.val)
            currentLevelNum -= 1
            if node.left:
                queue.append(node.left)
                nextLevelNum += 1
            if node.right:
                queue.append(node.right)
                nextLevelNum += 1
            if currentLevelNum == 0:
                if level % 2 == 1:
                    resultList.append(levelList)
                else:
                    levelList.reverse()
                    resultList.append(levelList)
                levelList = []
                currentLevelNum = nextLevelNum
                nextLevelNum = 0
                level += 1
        return resultList