之前我們探索了數(shù)組、字典、字符串、鏈表、棧、隊(duì)列的處理和應(yīng)用。今天我們來講講平常相對很少用到，面試中卻是老面孔的數(shù)據(jù)結(jié)構(gòu)：二叉樹。本期的內(nèi)容有：
- 基本概念：實(shí)現(xiàn)，深度 ，二叉查找樹
- 遍歷
- 蘋果面試題：在iOS中展示二叉樹
概念
首先介紹下二叉樹。二叉樹中每個節(jié)點(diǎn)最多有兩個子節(jié)點(diǎn)，一般稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)，并且二叉樹的子樹有左右之分，其次序不能任意顛倒。下面是節(jié)點(diǎn)的Swift實(shí)現(xiàn)：
public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init(_val: Int) {
self.val = val
}
}
一般在面試中，會給定二叉樹的根節(jié)點(diǎn)。要訪問任何其他節(jié)點(diǎn)，只要從起始節(jié)點(diǎn)開始往左/右走即可。
在樹中，節(jié)點(diǎn)的層次從根開始定義，根為第一層，樹中節(jié)點(diǎn)的最大層次為樹的深度。
// 計算樹的最大深度
func maxDepth(root: TreeNode?) -> Int {
guard let root = root else {
return 0
}
return max(maxDepth(root.left), maxDepth(root.right)) + 1
}
面試中，最常見的是二叉查找樹，它是一種特殊的二叉樹。它的特點(diǎn)就是左子樹中節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值，右子樹中節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值。那么問題來了，給你一棵二叉樹，怎么判斷它是二叉查找樹？我們根據(jù)定義，可以寫出以下解法：
// 判斷一顆二叉樹是否為二叉查找樹
func isValidBST(root: TreeNode?) -> Bool {
return _helper(root, nil, nil)
}
private func _helper(node: TreeNode?, _ min: Int?, _ max: Int?) -> Bool {
guard let node = node else {
return true
}
// 所有右子節(jié)點(diǎn)都必須大于根節(jié)點(diǎn)
if let min = min, node.val <= min {
return false
}
// 所有左子節(jié)點(diǎn)都必須小于根節(jié)點(diǎn)
if let max = max, node.val >= max {
return false
}
return _helper(node.left, min, node.val) && _helper(node.right, node.val, max)
}
上面的代碼有這幾個點(diǎn)指點(diǎn)注意：
- 二叉樹本身是由遞歸定義的，所以原理上所有二叉樹的題目都可以用遞歸來解
- 二叉樹這類題目很容易就會牽涉到往左往右走，所以寫helper函數(shù)要想到有兩個相對應(yīng)的參數(shù)
- 記得處理節(jié)點(diǎn)為nil的情況，尤其要注意根節(jié)點(diǎn)為nil的情況
遍歷
最常見的樹的遍歷有三種，前序、中序、后序遍歷。這三種寫法相似，無非是遞歸的順序略有不同。面試時候有可能考察的是用非遞歸的方法寫這三種遍歷：用棧實(shí)現(xiàn)。
// 用棧實(shí)現(xiàn)的前序遍歷
func preorderTraversal(root: TreeNode?) -> [Int] {
var res = [Int]()
var stack = [TreeNode]()
var node = root
while !stack.isEmpty || node != nil {
if node != nil {
res.append(node!.val)
stack.append(node!)
node = node!.left
} else {
node = stack.removeLast().right
}
}
return res
}
除了這三種最常見的遍歷之外，還有一種遍歷是層級遍歷（廣度優(yōu)先遍歷），請看下圖：
這棵樹的層級遍歷結(jié)果為[[1], [2, 3], [4, 5, 6, 7], [8, 9, 10, 11, 12, 13, 14, 15]]。
層級遍歷相比于以上三種常見遍歷的好處在于：如果構(gòu)建一棵樹，那么至少要知道中序遍歷和前序/后序遍歷中的一種，也就是至少要知道兩種遍歷方式；但是層級遍歷自己便可以唯一確定一棵樹。我們來看下面一道蘋果公司的面試題。
實(shí)戰(zhàn)
Given a binary tree, please design an iOS app to demo it.
首先一個簡單的app是mvc架構(gòu)，所以我們就要想，在View的層面上表示一棵二叉樹？我們腦海中浮現(xiàn)樹的結(jié)構(gòu)是這樣的：
所以是不是在View的界面上，每個節(jié)點(diǎn)弄個UILabel來表示，然后用數(shù)學(xué)方法計算每個UIlabel對應(yīng)的位置，從而完美的顯示上圖的樣子？
這個想法比較簡單粗暴，是最容易想到，實(shí)現(xiàn)之后又是最直觀展示一棵二叉樹的，但是它有以下兩個問題：
- 每個UILabel的位置計算起來比較麻煩；
- 如果一棵樹有很多節(jié)點(diǎn)（比如1000個），那么當(dāng)前界面就會顯示不下了，這時候咋辦？就算用UIScrollView來處理，整個樹也會變得非常不直觀，每個節(jié)點(diǎn)所對應(yīng)的UILabel位置計算起來就會更費(fèi)力。
要處理大量數(shù)據(jù)，我們就想到了UITableView。假如每一個cell對應(yīng)一個節(jié)點(diǎn)，以及其左、右節(jié)點(diǎn)，那么我們就可以清晰的展示一棵樹。比如上圖這棵樹，用UITableView就可以寫成這樣：
其中"#"表示空節(jié)點(diǎn)。明眼人可以看出，我們是按照層級遍歷的方式布局整個UITableView。這種做法解決了上面兩個問題：
- 無需進(jìn)行位置計算，UITableView提供復(fù)用Cell，效率大幅提高
- 面對很多節(jié)點(diǎn)的問題，可以先處理一部分?jǐn)?shù)據(jù)，然后用處理infinite scroll的方式來加載剩余數(shù)據(jù)
接著問題來了，給你一棵二叉樹，如何得到它的層級遍歷？其實(shí)層級遍歷就是圖的廣度優(yōu)先遍歷，而廣度優(yōu)先遍歷很自然就會用到隊(duì)列，所以我們不妨用隊(duì)列來幫助實(shí)現(xiàn)樹的層級遍歷：
func levelOrder(root: TreeNode?) -> [[Int]] {
var res = [[Int]]()
// 用數(shù)組來實(shí)現(xiàn)隊(duì)列
var queue = [TreeNode]()
if let root = root {
queue.append(root)
}
while queue.count > 0 {
var size = queue.count
var level = [Int]()
for _ in 0 ..< size {
let node = queue.removeFirst()
level.append(node.val)
if let left = node.left {
queue.append(left)
}
if let right = node.right {
queue.append(right)
}
}
res.append(level)
}
return res
}
總結(jié)
到這里為止，我們已經(jīng)把重要的數(shù)據(jù)結(jié)構(gòu)都分析了一遍。要知道，這些數(shù)據(jù)結(jié)構(gòu)都不是單獨(dú)存在的，我們在解決二叉樹的問題時，用到了隊(duì)列；解決數(shù)組的問題，也會用到字典或是棧。在真正面試或是日常Coding中，最低的時間復(fù)雜度是首要考慮，接著是優(yōu)化空間復(fù)雜度，其次千萬不要忘記考慮特殊情況。在Swift中，用let和var的地方要區(qū)分清楚，該不該定義數(shù)據(jù)為optional，有沒有處理nil的情況都是很容易忽略的，希望大家多多練習(xí)，融會貫通。
