27. Binary Tree Zigzag Level Order Traversal

読了目安約1分

Tree / LC 103 (Medium) — レベルごとに向きを反転して走査する。

この章の目次

問題

LeetCode 103. Binary Tree Zigzag Level Order Traversal（Medium / カテゴリ: Tree）

前問と同じレベルごとの走査ですが、値を並べる向きをレベルごとに交互に変えます。 1 レベル目は左から右、2 レベル目は右から左、3 レベル目はまた左から右です。

考え方

ヒント 1

木のたどり方は Level Order Traversal と同じです。変わるのは「結果に記録するときの向き」だけです。

ヒント 2

「今は左から右か」を表す Bool を 1 つ持ち、レベルを進むたびに反転します。右から左のレベルでは、値の配列を反転してから結果に追加します。

Swift 実装のポイント

探索の順序は変えず、記録時に reversed() で反転するのが簡単です。
values.reversed() の戻り値は ReversedCollection なので、Array(values.reversed()) で配列に戻します。
Bool の反転は leftToRight.toggle() と書けます。

模範解答

Swift
class Solution {
    func zigzagLevelOrder(_ root: TreeNode?) -> [[Int]] {
        guard let root = root else { return [] }
        var result: [[Int]] = []
        var level = [root]
        var leftToRight = true
        while !level.isEmpty {
            let values = level.map { $0.val }
            result.append(leftToRight ? values : Array(values.reversed()))
            leftToRight.toggle()
            var next: [TreeNode] = []
            for node in level {
                if let left = node.left { next.append(left) }
                if let right = node.right { next.append(right) }
            }
            level = next
        }
        return result
    }
}

計算量: O(N)。反転を含めても各ノードは定数回しか触りません。