翻转二叉树之Swift实践

Google: 90% of our engineers use the software you wrote(HomeBrew), but you can’t invert a binary tree on a whiteboard so fuck off.

HomeBrew作者,天才程序员Max Howell兴致盎然地去Google面试(估计是刚好路过),结果却因不会在白板上翻转二叉树被Google粗鲁地拒绝了,舆论甚是哗然,其中缘由知乎上也讨论的热火朝天。谁料,始作俑者翻转二叉树这道题目,一时也热地不要不要的。作为程序员小白的我,从未翻过二叉树。最近闲来无事,闲暇之余,想及至此,就顺手用Swift翻转了二叉树。

如果您对二叉树的概念不甚清晰,可以先到维基百科上(不推荐百度百科,因为要养成良好的搜索习惯)再温习温习二叉树相关知识。

二叉树定义

先定义一个二叉树类Tree,主要定义树的三个必要属性,关键值key,左子树leftTree和右子树rightTree

1
2
3
4
5
6
7
8
9
10
11
//define Tree class
class Tree {
var key: Int
var leftTree: Tree?
var rightTree: Tree?

init(key: Int) {
self.key = key
}

}

递归翻转

用递归的方式翻转二叉树,主要分为两步:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//invert binary tree using recursive
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步:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//invert binary tree without using recursive
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)。

遍历二叉树

为了遍历二叉树,输出有树形状的结果,先定义一个辅助函数,计算树的高度.

计算树的高度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//calculate the height of a tree using recursive
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步:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//print out binary tree in the shape of tree when the key is less than 10
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)。

测试

生成二叉树,并进行测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
let tree = Tree(key: 1)
tree.leftTree = Tree(key: 2)
tree.rightTree = Tree(key: 3)
tree.leftTree?.leftTree = Tree(key: 4)
tree.leftTree?.leftTree?.leftTree = Tree(key: 6)
tree.rightTree?.leftTree = Tree(key: 7)
tree.leftTree?.leftTree?.rightTree = Tree(key: 5)

print("------tree before inverting-------")
tranverseTree(tree)
print("------tree inverted-------")
invertBinaryTreeWithRecursive(tree)
tranverseTree(tree)

输出结果为:

1
2
3
4
5
6
7
8
9
10
------tree before inverting-------
1
2 3
4 7
6 5
------tree inverted-------
1
3 2
7 4
5 6

感悟

纵观上述二叉树翻转过程,用的知识较难的无非就是递归,而递归作为编程的精髓,学习稍微深入,就难以避免,而Max Howell竟然不会,或许是久疏战阵,髀肉横生吧。也说明互联网知识繁多,常常难以多头兼顾,记住所有知识,我们应保持一颗积极学习的心态。

分享到 评论