Swift刷算法：二叉树的Z形层序遍历

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

LeetCode：https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal

/**
* Definition for a binary tree node.
* public class TreeNode {
*     public var val: Int
*     public var left: TreeNode?
*     public var right: TreeNode?
*     public init() { self.val = 0; self.left = nil; self.right = nil; }
*     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
*     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
*         self.val = val
*         self.left = left
*         self.right = right
*     }
* }
*/
class Solution {
   func zigzagLevelOrder(_ root: TreeNode?) -> [[Int]] {
       // 排除根节点为空的情况
       guard let root = root else { return [] }
       // 保存最终结果
       var res: [[Int]] = []
       // 当前遍历到的层级的结果
       var ans: [Int] = []
       // 遍历到的节点队列，会动态增删，初始化为一个根结点
       var queue: [TreeNode] = [root]
       // 当前层级
       var level = 1

       // 循环遍历直至队列为空
       while !queue.isEmpty {
           // 该值其实就是当前层级的节点个数，因为在for循环中队列可能会增加，所以提前取出
           let size = queue.count
           // 读取队列前size个节点加入ans
           for i in 0 ..< size {
               // Z字形遍历，取出节点值
               if level % 2 != 0 {
                   // 单数层追加到ans末尾
                   ans.append(queue[i].val)
               } else {
                   // 双数层插入到ans头部
                   ans.insert(queue[i].val, at: 0)
               }

               // 看看当前节点是否有左孩子，有的话加入遍历队列queue末尾
               if let left = queue[i].left {
                   queue.append(left)
               }

               // 看看当前节点是否有右孩子，有的话加入遍历队列queue末尾
               if let right = queue[i].right {
                   queue.append(right)
               }
           }

           // 本层级for循环结束，将层级结果加入最终结果数组
           res.append(ans)
           // 清空层级结果数组
           ans.removeAll()
           // 删除队列前size个已经遍历完的节点
           queue.removeFirst(size)
           // 准备遍历下一层级
           level += 1 
       }

       // 返回最终结果
       return res
   }
}

image.png