Đề bài: Duyệt cây nhị phân level order nhưng chiều xen kẽ: level 0 left→right, level 1 right→left, level 2 left→right...
Ví dụ: Tree [3,9,20,null,null,15,7] → [[3],[20,9],[15,7]].
Giải pháp 1: BFS + Flag (Đơn Giản)
BFS chuẩn, mỗi level thu thập nodes. Nếu level lẻ → reverse list trước khi add vào result.
from collections import deque
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: TreeNode) -> list[list[int]]:
if not root:
return []
result = []
queue = deque([root])
left_to_right = True
while queue:
level_size = len(queue)
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if not left_to_right:
level.reverse()
result.append(level)
left_to_right = not left_to_right
return result
Giải pháp 2: Two Stacks (Không Cần Reverse)
Stack1: level hiện tại (left→right). Stack2: level tiếp theo (right→left). Pop từ stack1, push children vào stack2 theo thứ tự left→right. Pop từ stack2, push children vào stack1 theo thứ tự right→left.
def zigzagLevelOrder(self, root):
if not root: return []
s1, s2 = [root], []
result = []
while s1 or s2:
level = []
while s1:
node = s1.pop()
level.append(node.val)
if node.left: s2.append(node.left)
if node.right: s2.append(node.right)
if level: result.append(level)
level = []
while s2:
node = s2.pop()
level.append(node.val)
if node.right: s1.append(node.right)
if node.left: s1.append(node.left)
if level: result.append(level)
return result
Phân tích
| Phương pháp | Time | Space | Ghi chú |
|---|---|---|---|
| BFS + Reverse | O(n) | O(w) | w = max width. Simple, readable. |
| Two Stacks | O(n) | O(w) | No reverse, but more complex logic. |
Kết luận
BFS + reverse flag là giải pháp phổ biến nhất, dễ hiểu, dễ maintain. Two stacks thú vị nhưng dễ bug. Đề bài thường chấp nhận cả hai.