HomeBrew作者，天才程序员Max Howell去Google面试），结果却因不会在白板上翻转二叉树被Google粗鲁地拒绝了，舆论甚是哗然，其中缘由知乎上也讨论的热火朝天。谁料，始作俑者翻转二叉树。作为程序猿的我，从未翻过二叉树。最近闲来无事，闲暇之余，想及至此，就顺手用Swift翻转了二叉树。
1.需求如下图
2.二叉树定义
先定义一个二叉树类Tree，主要定义树的三个必要属性，关键值key，左子树leftTree和右子树rightTree。
class Tree {
var key: Int //节点上显示的关键值
var leftTree: Tree? //左子树
var rightTree: Tree? //右子树
//初始化方法
init(key: Int) {
self.key = key
}
}
3. 解决方案
3.1 递归翻转
用递归的方式翻转二叉树，主要分为两步：
func invertBinaryTreeWithRecursive(root: Tree) {
//1
let tempT = root.leftTree
root.leftTree = root.rightTree
root.rightTree = tempT
//2
if let leftT = root.leftTree {
//递归调用
invertBinaryTreeWithRecursive(leftT)
}
if let rightT = root.rightTree {
invertBinaryTreeWithRecursive(rightT)
}
}
第1步：翻转本树的左子树和右子树，需要借助一个零时变量tempT；
第2步：判断左右树是否存在，如存在，则递归调用进行翻转。
递归翻转二叉树每个节点只访问1次，在每个节点上的耗时是常数，因此总耗时Θ(n)，n是树的节点树。
3.2 非递归翻转
其实也可以不用递归翻转二叉树，分为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步：初始化一个数组，用来存储尚未翻转的树，第一个尚未翻转的树即是根树；
第2步：判断是否仍有树未翻转，如果有，从数组中取出第一个树，并将它从数组中删除，然后对这个树翻转左子树和右子树，需要借助一个零时变量tempT；
第3步：判断被翻的树左右子树是否存在，如存在，将它依次存储在数组的最后面。
这种翻转二叉树的方式是从左到右翻完同一层的树节点，再从左到右翻下一层的树节点，直至翻完，其耗时也是Θ(n)。
4. 遍历二叉树
为了遍历二叉树，输出有树形状的结果，先定义一个辅助函数，计算树的高度.
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步：返回左右子树高度的最大值，这一步是递归终止条件，是整个递归的精髓。
因为遍历了所有树节点，因此总耗时Θ(n)。
4.2 遍历
为输出的结果具有树的形状，树的遍历输出要费点脑筋，分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步：初始化一个数组，存储元组类型(tree: Tree, number: Int, height: Int, depth: Int, placeHolderTree: Bool)；这个元组中tree表示一个树节点；number表示这个树节点在其所在层的位置，第一个number为1，第二个number为2，依次类推；height表示这个树节点的高度；depth表示这个树节点的深度；placeHolderTree表示这个树节点是否为占位树。为便于后续遍历，当树为非完全二叉树时，空缺的树节点全部用占位树填补，因此才有placeHolderTree
元组元素，以标示占位树；
第2步：这是一个utility函数，在第4步时调用；
第3步：判断树是否到底，当没到底时，从数组中取出并删除第一个节点，然后计算并打印这个节点相应的空格数，然后打印节点key值，如果这个节点是同一层级最后一个节点，打印换行；
第4步：将这个节点的左右子树连同相应信息存储到数组中，这时调用了第2步中的utility函数appendTree:node:，appendTree:node:
中对传入的树节点进行了判断，当为空时，自动填补占位树。
此函数遍历了所有树节点，因此总耗时Θ(n)。
4.3 测试
生成二叉树，并进行测试：
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)
输出结果为：
------tree before inverting-------
1
2 3
4
------tree inverted-------
1
3 2
4
