解題代碼都是使用 Swift 完成的，我也盡量在代碼中使用了 Swift 語(yǔ)言的一些特性，大家可以順便學(xué)學(xué) Swift。
問(wèn)題:給你一棵二叉樹(shù)，請(qǐng)按層輸出其的節(jié)點(diǎn)值，即：按從上到下，從左到右的順序。
例如，如果給你如下一棵二叉樹(shù)：
? ?3
? / \
?9 ?20
? ?/ ?\
? 15 ? 7
輸出結(jié)果應(yīng)該是：
[
?[3],
?[9,20],
?[15,7]
]
本題的 Swift 代碼模版如下：
private class TreeNode {
? ?public var val: Int
? ?public var left: TreeNode?
? ?public var right: TreeNode?
? ?public init(_ val: Int) {
? ? ? ?self.val = val
? ? ? ?self.left = nil
? ? ? ?self.right = nil
? ?}
}
class Solution {
? ?func levelOrder(_ root: TreeNode?) -> [[Int]] {
? ?}
}
解答:本題出自 LeetCode 第 102 題，是一個(gè)典型的有關(guān)遍歷的題目。為了按層遍歷，我們需要使用「隊(duì)列」，來(lái)將每一層的節(jié)點(diǎn)先保存下來(lái)，然后再依次處理。
因?yàn)槲覀儾坏枰磳觼?lái)遍歷，還需要按層來(lái)輸出結(jié)果，所以我在代碼中使用了兩個(gè)隊(duì)列，分別名為 level 和 nextLevel，用于保存不同層的節(jié)點(diǎn)。
最終，整個(gè)算法邏輯是：
判斷輸入?yún)?shù)是否是為空。
將根節(jié)點(diǎn)加入到隊(duì)列 level 中。
如果 level 不為空，則：
3.1 將 level 加入到結(jié)果 ans 中。
3.2 遍歷 level 的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)，將其加入到 nextLevel 中。
3.3 將 nextLevel 賦值給 level，重復(fù)第 3 步的判斷。
將 ans 中的節(jié)點(diǎn)換成節(jié)點(diǎn)的值，返回結(jié)果。
因?yàn)槲覀兪怯?Swift 來(lái)實(shí)現(xiàn)代碼，所以我使用了一些 Swift 語(yǔ)言的特性。例如：隊(duì)列中我們保存的是節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，但是最終輸出的時(shí)候，我們需要輸出的是值，在代碼中，我使用了 Swift 的函數(shù)式的鏈?zhǔn)秸{(diào)用，將嵌套數(shù)組中的元素類(lèi)型做了一次變換，如下所示：
let ans = result.map { $0.map { $0.val }}
另外，我們也使用了 Swift 特有的 guard 關(guān)鍵字，來(lái)處理參數(shù)的特殊情況。
完整的參考代碼如下：
//
// ?Binary Tree Level Order Traversal.swift
//
// ?Created by Tang Qiao.
//
import Foundation
private class TreeNode {
? ?public var val: Int
? ?public var left: TreeNode?
? ?public var right: TreeNode?
? ?public init(_ val: Int) {
? ? ? ?self.val = val
? ? ? ?self.left = nil
? ? ? ?self.right = nil
? ?}
}
private class Solution {
? ?func levelOrder(_ root: TreeNode?) -> [[Int]] {
? ? ? ?guard let root = root else {
? ? ? ? ? ?return []
? ? ? ?}
? ? ? ?var result = [[TreeNode]]()
? ? ? ?var level = [TreeNode]()
? ? ? ?level.append(root)
? ? ? ?while level.count != 0 {
? ? ? ? ? ?result.append(level)
? ? ? ? ? ?var nextLevel = [TreeNode]()
? ? ? ? ? ?for node in level {
? ? ? ? ? ? ? ?if let leftNode = node.left {
? ? ? ? ? ? ? ? ? ?nextLevel.append(leftNode)
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?if let rightNode = node.right {
? ? ? ? ? ? ? ? ? ?nextLevel.append(rightNode)
? ? ? ? ? ? ? ?}
? ? ? ? ? ?}
? ? ? ? ? ?level = nextLevel
? ? ? ?}
? ? ? ?let ans = result.map { $0.map { $0.val }}
? ? ? ?return ans
? ?}
}
微信中排版代碼非常不便，所以上述代碼也可以從我的 Gist 中找到：代碼Gist地址
完成這道題的同學(xué)，可以試著練習(xí)一下 LeetCode的第 107 題，看看能不能只改動(dòng)一行代碼，就把 107 題也解決掉。
