之前我們探索了數(shù)組、字典倒戏、字符串怠噪、鏈表、棧峭梳、隊列的處理和應用舰绘。今天我們來講講平常相對很少用到，面試中卻是老面孔的數(shù)據(jù)結構：二叉樹葱椭。本期的內(nèi)容有：
- 基本概念：實現(xiàn)捂寿，深度 ，二叉查找樹
- 遍歷
- 蘋果面試題：在iOS中展示二叉樹
概念
首先介紹下二叉樹孵运。二叉樹中每個節(jié)點最多有兩個子節(jié)點秦陋，一般稱為左子節(jié)點和右子節(jié)點，并且二叉樹的子樹有左右之分治笨，其次序不能任意顛倒驳概。下面是節(jié)點的Swift實現(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é)點旷赖。要訪問任何其他節(jié)點顺又，只要從起始節(jié)點開始往左/右走即可。
在樹中等孵，節(jié)點的層次從根開始定義稚照，根為第一層，樹中節(jié)點的最大層次為樹的深度俯萌。
// 計算樹的最大深度
func maxDepth(root: TreeNode?) -> Int {
guard let root = root else {
return 0
}
return max(maxDepth(root.left), maxDepth(root.right)) + 1
}
面試中果录，最常見的是二叉查找樹，它是一種特殊的二叉樹咐熙。它的特點就是左子樹中節(jié)點的值都小于根節(jié)點的值弱恒，右子樹中節(jié)點的值都大于根節(jié)點的值。那么問題來了棋恼，給你一棵二叉樹返弹，怎么判斷它是二叉查找樹锈玉？我們根據(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é)點都必須大于根節(jié)點
if let min = min, node.val <= min {
return false
}
// 所有左子節(jié)點都必須小于根節(jié)點
if let max = max, node.val >= max {
return false
}
return _helper(node.left, min, node.val) && _helper(node.right, node.val, max)
}
上面的代碼有這幾個點指點注意：
- 二叉樹本身是由遞歸定義的琉苇，所以原理上所有二叉樹的題目都可以用遞歸來解
- 二叉樹這類題目很容易就會牽涉到往左往右走嘲玫，所以寫helper函數(shù)要想到有兩個相對應的參數(shù)
- 記得處理節(jié)點為nil的情況悦施，尤其要注意根節(jié)點為nil的情況
遍歷
最常見的樹的遍歷有三種并扇，前序、中序抡诞、后序遍歷穷蛹。這三種寫法相似，無非是遞歸的順序略有不同昼汗。面試時候有可能考察的是用非遞歸的方法寫這三種遍歷：用棧實現(xiàn)肴熏。
// 用棧實現(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)先遍歷）顷窒，請看下圖：
這棵樹的層級遍歷結果為[[1], [2, 3], [4, 5, 6, 7], [8, 9, 10, 11, 12, 13, 14, 15]]蛙吏。
層級遍歷相比于以上三種常見遍歷的好處在于：如果構建一棵樹，那么至少要知道中序遍歷和前序/后序遍歷中的一種鞋吉，也就是至少要知道兩種遍歷方式鸦做；但是層級遍歷自己便可以唯一確定一棵樹。我們來看下面一道蘋果公司的面試題谓着。
實戰(zhàn)
Given a binary tree, please design an iOS app to demo it.
首先一個簡單的app是mvc架構泼诱，所以我們就要想，在View的層面上表示一棵二叉樹赊锚？我們腦海中浮現(xiàn)樹的結構是這樣的：
所以是不是在View的界面上治筒，每個節(jié)點弄個UILabel來表示，然后用數(shù)學方法計算每個UIlabel對應的位置舷蒲，從而完美的顯示上圖的樣子耸袜？
這個想法比較簡單粗暴，是最容易想到牲平，實現(xiàn)之后又是最直觀展示一棵二叉樹的堤框，但是它有以下兩個問題：
- 每個UILabel的位置計算起來比較麻煩；
- 如果一棵樹有很多節(jié)點（比如1000個）欠拾，那么當前界面就會顯示不下了胰锌，這時候咋辦？就算用UIScrollView來處理藐窄，整個樹也會變得非常不直觀资昧，每個節(jié)點所對應的UILabel位置計算起來就會更費力。
要處理大量數(shù)據(jù)荆忍，我們就想到了UITableView格带。假如每一個cell對應一個節(jié)點撤缴，以及其左、右節(jié)點叽唱，那么我們就可以清晰的展示一棵樹屈呕。比如上圖這棵樹，用UITableView就可以寫成這樣：
其中"#"表示空節(jié)點棺亭。明眼人可以看出虎眨，我們是按照層級遍歷的方式布局整個UITableView。這種做法解決了上面兩個問題：
- 無需進行位置計算镶摘，UITableView提供復用Cell嗽桩，效率大幅提高
- 面對很多節(jié)點的問題，可以先處理一部分數(shù)據(jù)凄敢，然后用處理infinite scroll的方式來加載剩余數(shù)據(jù)
接著問題來了碌冶，給你一棵二叉樹，如何得到它的層級遍歷涝缝？其實層級遍歷就是圖的廣度優(yōu)先遍歷扑庞，而廣度優(yōu)先遍歷很自然就會用到隊列，所以我們不妨用隊列來幫助實現(xiàn)樹的層級遍歷：
func levelOrder(root: TreeNode?) -> [[Int]] {
var res = [[Int]]()
// 用數(shù)組來實現(xiàn)隊列
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
}
總結
到這里為止拒逮，我們已經(jīng)把重要的數(shù)據(jù)結構都分析了一遍罐氨。要知道，這些數(shù)據(jù)結構都不是單獨存在的消恍，我們在解決二叉樹的問題時岂昭，用到了隊列；解決數(shù)組的問題狠怨，也會用到字典或是棧约啊。在真正面試或是日常Coding中，最低的時間復雜度是首要考慮佣赖，接著是優(yōu)化空間復雜度恰矩，其次千萬不要忘記考慮特殊情況。在Swift中憎蛤，用let和var的地方要區(qū)分清楚外傅，該不該定義數(shù)據(jù)為optional，有沒有處理nil的情況都是很容易忽略的俩檬，希望大家多多練習萎胰，融會貫通。
