Binary Tree Zigzag Level Order Traversal: Level Order สลับทิศทาง (Zigzag)

โจทย์

กำหนด Binary Tree ทำ Zigzag Level Order Traversal:

Level 0 (root): ซ้าย → ขวา
Level 1: ขวา → ซ้าย
Level 2: ซ้าย → ขวา
สลับกันไปเรื่อยๆ

ตัวอย่าง:

Output: [[3], [20,9], [15,7]]

อัลกอริทึม 1: BFS + Deque (Double-ended Queue)

ใช้ deque สำหรับแต่ละ level: ถ้า left-to-right → append right, ถ้า right-to-left → append left

การติดตั้ง (Python Implementation - BFS + Deque)


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 = []
        q = deque([root])
        left_to_right = True
        
        while q:
            level_size = len(q)
            level = deque()
            
            for _ in range(level_size):
                node = q.popleft()
                
                if left_to_right:
                    level.append(node.val)
                else:
                    level.appendleft(node.val)
                
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            
            result.append(list(level))
            left_to_right = not left_to_right
        
        return result

# Helper
def build_tree(vals):
    if not vals:
        return None
    nodes = [TreeNode(v) if v is not None else None for v in vals]
    for i, node in enumerate(nodes):
        if node:
            li, ri = 2*i+1, 2*i+2
            if li < len(nodes):
                node.left = nodes[li]
            if ri < len(nodes):
                node.right = nodes[ri]
    return nodes[0]

# ทดสอบ
ob = Solution()
root = build_tree([3,9,20,None,None,15,7])
print(ob.zigzagLevelOrder(root))  # [[3], [20, 9], [15, 7]]

Output

[[3], [20, 9], [15, 7]]

อัลกอริทึม 2: BFS + Reverse (Simple)

BFS ปกติเก็บ level แล้ว reverse ทุก level ที่เป็นเลขคู่ (1-indexed) หรือคี่ (0-indexed)


def zigzagLevelOrder_simple(self, root):
    if not root:
        return []
    
    result = []
    q = deque([root])
    level = 0
    
    while q:
        level_size = len(q)
        current_level = []
        
        for _ in range(level_size):
            node = q.popleft()
            current_level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        
        if level % 2 == 1:
            current_level.reverse()
        result.append(current_level)
        level += 1
    
    return result

อัลกอริทึม 3: Two Stacks (DFS-style)

ใช้ 2 stacks: current_level และ next_level สลับทิศทางการ push children


def zigzagLevelOrder_two_stacks(self, root):
    if not root:
        return []
    
    result = []
    current = [root]
    next_level = []
    left_to_right = True
    
    while current:
        level_vals = []
        while current:
            node = current.pop()
            level_vals.append(node.val)
            
            if left_to_right:
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)
            else:
                if node.right:
                    next_level.append(node.right)
                if node.left:
                    next_level.append(node.left)
        
        result.append(level_vals)
        current, next_level = next_level, current
        left_to_right = not left_to_right
    
    return result

Complexity

Time: O(n) - เยี่ยมทุกโหนด 1 ครั้ง
Space: O(w) - w = maximum width of tree (queue/stack size)

สรุป

Zigzag Level Order Traversal มีหลายวิธี: BFS + Deque (efficient, no reverse needed), BFS + Reverse (simple, readable), Two Stacks (iterative DFS style) ทุกวิธี O(n) time

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ