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]
]
这个题目的思路也是典型的BFS, 只是每一层分别正序和倒序, 我还是利用102. Binary Tree Level Order Traversal_Medium tag: BFS的思路,只是多加了一个len(ans)%2== 0 去判断是应该正序还是倒序, 如果是倒序, 就把temp reverse然后append进入ans里面即可.
1. Constraints
1) edge case, root is None
2. Ideas
BFS: T: O(n) S: O(n)
3.code:
class Solution:
def zigzagLevel(self, root):
ans = []
if not root: return ans # edge case
queue = collections.deque([root])
while queue:
size, level = len(queue), []
for _ in range(size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if len(ans)%2 ==0:
ans.append(level)
else:
ans.append(level[::-1])
return ans