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).
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]
]
Solution
常犯的错误是按照层数的奇偶变化来决定插入头部还是尾部，而不是level内部的奇偶变化。
DFS
a前序遍历但是是动态层数，所以也可以实现。
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: The root of binary tree.
@return: A list of list of integer include
the zig zag level order traversal of its nodes' values
"""
def preorder(self, root, level, res):
if root:
if len(res) < level+1: res.append([])
if level % 2 == 0:
res[level].append(root.val)
else:
res[level].insert(0, root.val)
self.preorder(root.left, level+1, res)
self.preorder(root.right, level+1, res)
def zigzagLevelOrder(self, root):
self.results = []
self.preorder(root, 0, self.results)
return self.results
class Solution:
"""
@param root: The root of binary tree.
@return: A list of list of integer include
the zig zag level order traversal of its nodes' values
"""
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root == None:
return []
result = []
queue = collections.deque([root])
m = 0
while queue:
level = []
for i in range(len(queue)):
node = queue.popleft()
if m % 2 == 0:
level.append(node.val)
else:
level.insert(0, node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
m += 1
return result