給你二叉樹的根節(jié)點 root 缩膝，返回其節(jié)點值的 鋸齒形層序遍歷 搭幻。（即先從左往右，再從右往左進(jìn)行下一層遍歷逞盆，以此類推，層與層之間交替進(jìn)行）松申。
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]] {
// 排除根節(jié)點為空的情況
guard let root = root else { return [] }
// 保存最終結(jié)果
var res: [[Int]] = []
// 當(dāng)前遍歷到的層級的結(jié)果
var ans: [Int] = []
// 遍歷到的節(jié)點隊列云芦，會動態(tài)增刪俯逾，初始化為一個根結(jié)點
var queue: [TreeNode] = [root]
// 當(dāng)前層級
var level = 1
// 循環(huán)遍歷直至隊列為空
while !queue.isEmpty {
// 該值其實就是當(dāng)前層級的節(jié)點個數(shù)，因為在for循環(huán)中隊列可能會增加舅逸，所以提前取出
let size = queue.count
// 讀取隊列前size個節(jié)點加入ans
for i in 0 ..< size {
// Z字形遍歷桌肴，取出節(jié)點值
if level % 2 != 0 {
// 單數(shù)層追加到ans末尾
ans.append(queue[i].val)
} else {
// 雙數(shù)層插入到ans頭部
ans.insert(queue[i].val, at: 0)
}
// 看看當(dāng)前節(jié)點是否有左孩子，有的話加入遍歷隊列queue末尾
if let left = queue[i].left {
queue.append(left)
}
// 看看當(dāng)前節(jié)點是否有右孩子琉历，有的話加入遍歷隊列queue末尾
if let right = queue[i].right {
queue.append(right)
}
}
// 本層級for循環(huán)結(jié)束坠七，將層級結(jié)果加入最終結(jié)果數(shù)組
res.append(ans)
// 清空層級結(jié)果數(shù)組
ans.removeAll()
// 刪除隊列前size個已經(jīng)遍歷完的節(jié)點
queue.removeFirst(size)
// 準(zhǔn)備遍歷下一層級
level += 1
}
// 返回最終結(jié)果
return res
}
}
image.png
