HomeBrew作者去Google面试做错的一道题，影响很大，大家一定要研究下这道题。

事件回放

2015 年 6 月 10 日，Homebrew 的作者 @Max Howell 在 twitter 上发表了如下一内容：

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.

事情大概是说，Max Howell 去 Google 面试，

面试官说：虽然在 Google 有 90% 的工程师用你写的 Homebrew，但是你居然不能在白板上写出翻转二叉树的代码，所以滚蛋吧。

这件事情如果发生在任何一个应届生身上，那是再正常不过的了，但是偏偏面试者是有名的 Max Howell。于是乎，关于应该如何面试程序员，再一次被大家热烈的讨论。知乎上也有相关的讨论，如何看待 Max Howell 被 Google 拒绝？
大家也可以看一下 Quora 和 Hacker News 上的讨论。

题目

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

解题思路

翻转一个二叉树，直观上看，就是把二叉树的每一层左右顺序倒过来。比如问题中的例子，第三层1-3-6-9经过变换后变成了9-6-3-1，顺序反过来就对了。 再仔细观察一下，对于上面的例子，根节点（root）的左子节点及其所有的子孙节点构成根节点的左子树（left subtree），同样的，根节点（root）的右子节点及其所有的子孙节点构成根节点的右子树（right subtree）。因此翻转一个二叉树，就是把根节点的左子树翻转一下，同样的把右子树翻转一下，在交换左右子树就可以了。 左子树和右子树

当然，翻转左子树和右子树的过程和当前翻转二叉树的过程没有区别，就是递归的调用当前的函数就可以了。 因此，翻转二叉树的步骤可总结如下：

1. 翻转根节点的左子树（递归调用当前函数）
2. 翻转根节点的右子树（递归调用当前函数）
3. 交换根节点的左子节点与右子节点

代码

invertBinaryTree.go

package _226_Invert_Binary_Tree

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func InvertTree(root *TreeNode) *TreeNode {
    if nil == root {
        return nil
    }

    if nil != root.Left {
        InvertTree(root.Left)
    }

    if nil != root.Right {
        InvertTree(root.Right)
    }

    root.Left, root.Right = root.Right, root.Left

    return root
}

测试代码

invertBinaryTree_test.go

package _226_Invert_Binary_Tree

import (
    "testing"
    "fmt"
)

func InitNode(val int, left *TreeNode, right *TreeNode) (ret *TreeNode){
    ret = new(TreeNode)
    ret.Val = val
    ret.Left = left
    ret.Right = right

    return ret
}


func treeEqual(t1 *TreeNode, t2 *TreeNode) bool{
    if t1.Val != t2.Val {
        return false
    }

    if nil == t1.Left && nil != t2.Left {
        return false
    }else if nil != t1.Left && nil == t2.Left {
        return false
    } else if nil != t1.Left && nil != t2.Left {
        left := treeEqual(t1.Left, t2.Left)
        if !left {
            return false
        }
    }

    if nil == t1.Right && nil != t2.Right {
        return false
    }else if nil != t1.Right && nil == t2.Right {
        return false
    }else if nil != t1.Right && nil != t2.Right {
        right := treeEqual(t1.Right, t2.Right)
        if !right {
            return false
        }
    }

    return true
}

func TreePrint(t1 *TreeNode) {

    if nil == t1 {
        fmt.Printf("null, ")
        return
    } else {
        fmt.Printf("%+v, ", t1.Val)
    }

    TreePrint(t1.Left)
    TreePrint(t1.Right)
}

func TestInvertTree(t *testing.T) {
    l3_1 := InitNode(1, nil, nil)
    l3_2 := InitNode(3, nil, nil)
    l3_3 := InitNode(6, nil, nil)
    l3_4 := InitNode(9, nil, nil)

    l2_1 := InitNode(2, l3_1, l3_2)
    l2_2 := InitNode(7, l3_3, l3_4)

    input := InitNode(4, l2_1, l2_2)



    w2_1 := InitNode(7, l3_4, l3_3)
    w2_2 := InitNode(2, l3_2, l3_1)

    want := InitNode(4, w2_1, w2_2)

    ret := InvertTree(input)

    equal := treeEqual(want, ret)

    TreePrint(want)
    fmt.Println()
    TreePrint(ret)
    fmt.Println()

    if equal {
        t.Logf("pass")
    } else {
        t.Errorf("fail, want %+v, get %+v", want, ret)
    }
}