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] ]
之字形层序遍历树
思路：设立一个标志位，当这个标志位为0时候，从左到右打印，当标志位为1时候，从右往左打印，每遍历一层，标志位变一次
1 class Solution(object): 2 def zigzagLevelOrder(self, root): 3 res,level = [],[root] 4 flag = 0 5 while root and level: 6 if not flag: 7 res.append([r.val for r in level]) 8 else: 9 res.append([r.val for r in level[::-1]]) 10 flag = 1-flag 11 pair = [(v.left,v.right) for v in level] 12 level = [v for lr in pair for v in lr if v] 13 return res
改：
1 class Solution(object): 2 def zigzagLevelOrder(self, root): 3 res,level,flag= [],[root],1 4 while root and level: 5 res.append([r.val for r in level[::flag]]) 6 flag *= -1 7 pair = [(v.left,v.right) for v in level] 8 level = [v for lr in pair for v in lr if v] 9 return res
[leetcode tree]103. Binary Tree Zigzag Level Order Traversal
原文：http://www.cnblogs.com/fcyworld/p/6524933.html