103. Binary Tree Zigzag Level Order Traversal

Medium
Description

給定一棵二元樹的根節點，回傳其鋸齒形層序遍歷（Zigzag Level Order）。即先從左到右，下一層從右到左，交替進行。

Example:

Input: root = [3,9,20,null,null,15,7] Output: [[3],[20,9],[15,7]]

Intuition#

標準 BFS 層序遍歷，偶數層正序、奇數層反序即可。

  • 基本架構與普通的層序遍歷 (102) 相同
  • 唯一差異是交替層需要反轉節點值的順序
  • 可以用一個布林旗標控制方向

Approaches#

⭐ 1: BFS with Direction Flag#

  • 概念: BFS 層序遍歷，用旗標控制每層是正序還是反序加入結果
  • 時間複雜度: O(n)，每個節點訪問一次
  • 空間複雜度: O(n)，佇列最多存放一層的節點
class Solution {
    fun zigzagLevelOrder(root: TreeNode?): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        if (root == null) return result
        val queue = ArrayDeque<TreeNode>()
        queue.add(root)
        var leftToRight = true
        while (queue.isNotEmpty()) {
            val size = queue.size
            val level = ArrayDeque<Int>()
            repeat(size) {
                val node = queue.removeFirst()
                if (leftToRight) {
                    level.addLast(node.`val`)
                } else {
                    level.addFirst(node.`val`)
                }
                node.left?.let { queue.add(it) }
                node.right?.let { queue.add(it) }
            }
            result.add(level.toList())
            leftToRight = !leftToRight
        }
        return result
    }
}

2: BFS + Reverse#

  • 概念: 正常 BFS 層序遍歷，奇數層直接反轉結果列表
  • 時間複雜度: O(n)
  • 空間複雜度: O(n)
class Solution {
    fun zigzagLevelOrder(root: TreeNode?): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        if (root == null) return result
        val queue = ArrayDeque<TreeNode>()
        queue.add(root)
        var level = 0
        while (queue.isNotEmpty()) {
            val size = queue.size
            val levelList = mutableListOf<Int>()
            repeat(size) {
                val node = queue.removeFirst()
                levelList.add(node.`val`)
                node.left?.let { queue.add(it) }
                node.right?.let { queue.add(it) }
            }
            if (level % 2 == 1) levelList.reverse()
            result.add(levelList)
            level++
        }
        return result
    }
}

🔑 Takeaways#

  • Pattern: BFS 層序遍歷的變形 — 加上方向控制
  • 關鍵技巧: 使用 ArrayDeque 的 addFirst / addLast 可以避免反轉操作，更優雅地控制插入方向