# 问题 原题链接：[https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/](https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/) Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree {3,9,20,#,#,15,7}, ``` 3 / \ 9 20 / \ 15 7 ``` return its zigzag level order traversal as: ``` [ [3], [20,9], [15,7] ] ``` # 分析过程 - 输入：二叉树 - 输出：之字形遍历结果 - 思路：利用队列进行广度优先搜索，分层记录。偶数层利用栈反序一次。 # 解决方法 ```swift class Solution { func zigzagLevelOrder(_ root: TreeNode?) -> [[Int]] { guard let root = root else { return [] } // 分层结果 var result = [[TreeNode]]() // 临时队列 var queue = [TreeNode]() // 记录层数用来之字形反序 var level = -1 // 广度搜索，根节点弹出队列，把左右子节点入队列，就能拿到该层的所有节点了 queue.append(root) while queue.count != 0 { result.append([TreeNode]()) level += 1 for _ in 0..<queue.count { let first = queue.removeFirst() // zigzag if level % 2 == 0 { result[level].append(first) } else { // 这里需要反向，偷懒用了insert，最好用栈 result[level].insert(first, at: 0) } if first.left != nil { queue.append(first.left!) } if first.right != nil { queue.append(first.right!) } } } return result.map { $0.map { $0.val } } } } ```