LEETCODE 103. 二叉树的锯齿形层次遍历
题目描述
给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
例如:
给定二叉树 [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 res0 次阅读