Zigzag Level Order Traversal

题目描述

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).

For 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]
]

解题方法

同level order,用一个变量记录当前的层数即可

Solution

from collections import deque
# 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 zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        queue = deque()
        result = []
        curList = []
        level = 1
        curNum = 1
        nextNum = 0
        queue.append(root)
        while queue:
            cur = queue.popleft()
            curNum -= 1
            curList.append(cur.val)
            if cur.left:
                queue.append(cur.left)
                nextNum += 1
            if cur.right:
                queue.append(cur.right)
                nextNum += 1
            if curNum == 0:
                curNum = nextNum
                nextNum = 0
                if level % 2 == 0:
                    curList.reverse()
                result.append(list(curList))
                curList = []
                level += 1

        return result

Reference