HomeBrew作者断序，天才程序員Max Howell去Google面試）奸汇，結(jié)果卻因不會在白板上翻轉(zhuǎn)二叉樹被Google粗魯?shù)鼐芙^了颤练，輿論甚是嘩然她倘，其中緣由知乎上也討論的熱火朝天。誰料铅祸，始作俑者翻轉(zhuǎn)二叉樹。作為程序猿的我合武，從未翻過二叉樹临梗。最近閑來無事，閑暇之余稼跳，想及至此盟庞，就順手用Swift翻轉(zhuǎn)了二叉樹。
1.需求如下圖
2.二叉樹定義
先定義一個二叉樹類Tree汤善，主要定義樹的三個必要屬性什猖，關(guān)鍵值key，左子樹leftTree和右子樹rightTree红淡。
class Tree {
var key: Int //節(jié)點上顯示的關(guān)鍵值
var leftTree: Tree? //左子樹
var rightTree: Tree? //右子樹
//初始化方法
init(key: Int) {
self.key = key
}
}
3. 解決方案
3.1 遞歸翻轉(zhuǎn)
用遞歸的方式翻轉(zhuǎn)二叉樹不狮，主要分為兩步：
func invertBinaryTreeWithRecursive(root: Tree) {
//1
let tempT = root.leftTree
root.leftTree = root.rightTree
root.rightTree = tempT
//2
if let leftT = root.leftTree {
//遞歸調(diào)用
invertBinaryTreeWithRecursive(leftT)
}
if let rightT = root.rightTree {
invertBinaryTreeWithRecursive(rightT)
}
}
第1步：翻轉(zhuǎn)本樹的左子樹和右子樹，需要借助一個零時變量tempT在旱；
第2步：判斷左右樹是否存在摇零，如存在，則遞歸調(diào)用進(jìn)行翻轉(zhuǎn)桶蝎。
遞歸翻轉(zhuǎn)二叉樹每個節(jié)點只訪問1次驻仅，在每個節(jié)點上的耗時是常數(shù)，因此總耗時Θ(n)登渣，n是樹的節(jié)點樹噪服。
3.2 非遞歸翻轉(zhuǎn)
其實也可以不用遞歸翻轉(zhuǎn)二叉樹，分為3步：
func invertBinaryTreeWithoutRecursive(root: Tree) {
//1
var arr = [Tree]()
arr.append(root)
//2
while !arr.isEmpty {
let node = arr.removeFirst()
let tempT = node.leftTree
node.leftTree = node.rightTree
node.rightTree = tempT
//3
if let leftT = node.leftTree {
arr.append(leftT)
}
if let rightT = node.rightTree {
arr.append(rightT)
}
}
}
第1步：初始化一個數(shù)組胜茧，用來存儲尚未翻轉(zhuǎn)的樹粘优，第一個尚未翻轉(zhuǎn)的樹即是根樹；
第2步：判斷是否仍有樹未翻轉(zhuǎn)竹揍，如果有敬飒，從數(shù)組中取出第一個樹，并將它從數(shù)組中刪除芬位，然后對這個樹翻轉(zhuǎn)左子樹和右子樹无拗，需要借助一個零時變量tempT；
第3步：判斷被翻的樹左右子樹是否存在昧碉，如存在英染，將它依次存儲在數(shù)組的最后面揽惹。
這種翻轉(zhuǎn)二叉樹的方式是從左到右翻完同一層的樹節(jié)點，再從左到右翻下一層的樹節(jié)點四康，直至翻完搪搏，其耗時也是Θ(n)。
4. 遍歷二叉樹
為了遍歷二叉樹闪金，輸出有樹形狀的結(jié)果疯溺，先定義一個輔助函數(shù)，計算樹的高度.
4.1 計算樹的高度
//calculate the height of a tree
func heightOfTree(root: Tree) -> Int {
//1
var leftTreeHeight = 0
var rightTreeHeight = 0
//2
if let leftT = root.leftTree {
leftTreeHeight = 1 + heightOfTree(leftT)
}
if let rightT = root.rightTree {
rightTreeHeight = 1 + heightOfTree(rightT)
}
//3
return max(leftTreeHeight, rightTreeHeight)
}
計算樹的高度也必須用到遞歸哎垦。
第1步：初始化兩個高度變量囱嫩，分別代表左右子樹高度，缺省值為0漏设，即左右子樹均為nil
時的值墨闲；
第2步：判斷左右子樹是否存在，如存在遞歸求左右子樹的高度郑口；
第3步：返回左右子樹高度的最大值鸳碧，這一步是遞歸終止條件，是整個遞歸的精髓犬性。
因為遍歷了所有樹節(jié)點瞻离，因此總耗時Θ(n)。
4.2 遍歷
為輸出的結(jié)果具有樹的形狀仔夺，樹的遍歷輸出要費(fèi)點腦筋琐脏，分4步：
//print out binary tree
func tranverseTree(root: Tree) {
//1
let height = heightOfTree(root)
var trees = [(tree: root, number: 1, height: height, depth: 0, placeHolderTree: false)]
let placeHolderTree = Tree(key: 0)
//2
func appendTree(tree: Tree?, node: (tree: Tree, number: Int, height: Int, depth: Int, placeHolderTree: Bool)) {
let number: Int
if let last = trees.last {
number = last.height == node.height - 1 ? last.number + 1 : 1
} else {
number = 1
}
if let t = tree {
trees.append((tree: t,
number: number,
height: node.height - 1,
depth: node.depth + 1,
placeHolderTree: false))
} else {
trees.append((tree: placeHolderTree,
number: number,
height: node.height - 1,
depth: node.depth + 1,
placeHolderTree: true))
}
}
//3
while trees[0].height >= 0 {
let node = trees.removeFirst()
let space: Int
if node.number == 1 {
space = Int(pow(2.0, Double(node.height)))
} else {
space = Int(pow(2.0, Double(node.height + 1)))
}
for _ in 1..<space {
print(" ", terminator: "")
}
if node.placeHolderTree {
print(" ", terminator: "")
} else {
print(node.tree.key, terminator: "")
}
if node.number == Int(pow(2.0, Double(node.depth))) {
print("")
}
//4
appendTree(node.tree.leftTree, node: node)
appendTree(node.tree.rightTree, node: node)
}
}
整個遍歷的思路與invertBinaryTreeWithoutRecursive完全一致。
第1步：初始化一個數(shù)組缸兔，存儲元組類型(tree: Tree, number: Int, height: Int, depth: Int, placeHolderTree: Bool)日裙；這個元組中tree表示一個樹節(jié)點；number表示這個樹節(jié)點在其所在層的位置惰蜜，第一個number為1昂拂，第二個number為2，依次類推抛猖；height表示這個樹節(jié)點的高度格侯；depth表示這個樹節(jié)點的深度；placeHolderTree表示這個樹節(jié)點是否為占位樹财著。為便于后續(xù)遍歷联四，當(dāng)樹為非完全二叉樹時，空缺的樹節(jié)點全部用占位樹填補(bǔ)撑教，因此才有placeHolderTree
元組元素朝墩，以標(biāo)示占位樹；
第2步：這是一個utility函數(shù)伟姐，在第4步時調(diào)用收苏；
第3步：判斷樹是否到底亿卤，當(dāng)沒到底時，從數(shù)組中取出并刪除第一個節(jié)點鹿霸，然后計算并打印這個節(jié)點相應(yīng)的空格數(shù)排吴，然后打印節(jié)點key值，如果這個節(jié)點是同一層級最后一個節(jié)點懦鼠，打印換行钻哩；
第4步：將這個節(jié)點的左右子樹連同相應(yīng)信息存儲到數(shù)組中，這時調(diào)用了第2步中的utility函數(shù)appendTree:node:葛闷，appendTree:node:
中對傳入的樹節(jié)點進(jìn)行了判斷憋槐，當(dāng)為空時，自動填補(bǔ)占位樹淑趾。
此函數(shù)遍歷了所有樹節(jié)點，因此總耗時Θ(n)忧陪。
4.3 測試
生成二叉樹扣泊，并進(jìn)行測試：
let tree = Tree(key: 1)
tree.leftTree = Tree(key: 2)
tree.rightTree = Tree(key: 3)
tree.rightTree?.leftTree = Tree(key: 4)
print("------tree before inverting-------")
tranverseTree(tree)
print("------tree inverted-------")
invertBinaryTreeWithRecursive(tree)
tranverseTree(tree)
輸出結(jié)果為：
------tree before inverting-------
1
2 3
4
------tree inverted-------
1
3 2
4
