二叉树的Z字形按层输出,BFS,每次处理一层,俺层数的奇偶正序or逆序append到结果list中
1 #103
2 #Runtime: 19 ms (Beats 68.89%)
3 #Memory: 13.6 MB (Beats 70.11%)
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 def zigzagLevelOrder(self, root):
13 """
14 :type root: TreeNode
15 :rtype: List[List[int]]
16 """
17
18 if not root:
19 return []
20 q = deque(([root]))
21 t = 0
22 ans = []
23 while(q):
24 sz = len(q)
25 tp = []
26 while sz > 0:
27 sz -= 1
28 node = q.popleft()
29 tp.append(node.val)
30 if node.left:
31 q.append(node.left)
32 if node.right:
33 q.append(node.right)
34 if t % 2:
35 ans.append(tp[::-1])
36 else:
37 ans.append(tp)
38 t += 1
39 return ans