HomeBrew作者，天才程序员Max Howell去Google面试），结果却因不会在白板上翻转二叉树被Google粗鲁地拒绝了，舆论甚是哗然，其中缘由知乎上也讨论的热火朝天。谁料，始作俑者翻转二叉树。作为程序猿的我，从未翻过二叉树。最近闲来无事，闲暇之余，想及至此，就顺手用Swift翻转了二叉树。

1.需求如下图

image.png

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