Solution
from typing import Optional, List
from collections import deque
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
ans = []
if root is None:
return ans
q = deque([root])
left = 1 # 1:从左向右；0:反转，从右向左
while q:
t = []
for _ in range(len(q)):
node = q.popleft()
t.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(t if left else t[::-1])
left ^= 1 # 异或1，0↔1来回翻转
return ans
# ----------------本地测试----------------
if __name__ == "__main__":
# 3
# / \
# 9 20
# / \
# 15 7
root = TreeNode(3,
TreeNode(9),
TreeNode(20, TreeNode(15), TreeNode(7))
)
print(Solution().zigzagLevelOrder(root))
# [[3], [20, 9], [15, 7]]
print(Solution().zigzagLevelOrder(None)) # []
print(Solution().zigzagLevelOrder(TreeNode(1))) # [[1]]