原题
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,null,null,15,7],3 / 9 20 / 15 7
return its zigzag level order traversal as:
[ [3], [20,9], [15,7] ]
# 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 root == None:
return []
stack, ret = [root], []
dep = 0
while stack:
level_value = []
next_level = []
for node in stack:
level_value.append(node.val)
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
if dep % 2 == 0:
ret.append(level_value)
else:
ret.append(level_value[::-1])
stack = next_level
dep += 1
return ret
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# 利用双向队列
# Your runtime beats 90.20 % of python submissions.
class Solution(object):
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root == None:
return []
DQ = collections.deque()
DQ.append(root)
ret = []
flag = True
while DQ:
length = len(DQ)
level_value = []
for i in xrange(length):
node = DQ.popleft()
if node.left:
DQ.append(node.left)
if node.right:
DQ.append(node.right)
if flag:
level_value.append(node.val)
else:
level_value = [node.val] + level_value
ret.append(level_value)
flag = not flag
return ret
LeetCode 103. Binary Tree Zigzag Level Order Traversal
原文：http://www.cnblogs.com/LiCheng-/p/6902775.html