问题描述
给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层序遍历如下：
[
[3],
[20,9],
[15,7]
]
解题思路
双栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
ltr, rtl = [root], []
ans = []
while ltr or rtl:
ans.append([])
if ltr:
while ltr:
node = ltr.pop()
ans[-1].append(node.val)
if node.left:
rtl.append(node.left)
if node.right:
rtl.append(node.right)
else:
while rtl:
node = rtl.pop()
ans[-1].append(node.val)
if node.right:
ltr.append(node.right)
if node.left:
ltr.append(node.left)
return ans
|
双队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | from collections import deque
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
q = deque([root])
f = False
ans = []
while q:
n = len(q)
t = deque([])
for _ in range(n):
node = q.popleft()
if f:
t.appendleft(node.val)
else:
t.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
f = not f
ans.append([])
while t:
ans[-1].append(t.popleft())
return ans
|