题目描述

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下：

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

题目地址
中文版
英文版

 

代码实现

BFS方式

# 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 = [root]
		res = []
		index = 0
		while queue:
			size = len(queue)
			tmp = []
			for _ in xrange(size):
				node = queue.pop(0)
				tmp.append(node.val)
				if(node.left!=None):
					queue.append(node.left)
				if(node.right!=None):
					queue.append(node.right)
			index += 1
			if(index%2==0):
				tmp.reverse()
				res.append(tmp)
			else:
				res.append(tmp)
		return res
			                                            

0 次阅读