会翻二叉树，咱就能去谷歌啦?

[YIXUNFE]

会翻二叉树，咱就能去谷歌啦?

前几天圈子里好不闹热，从 FP（函数式编程）到 OOP（面向对象编程），从切页面到算法数据结构，孰轻孰重，争论不休，还惊动了不少知名程序员。这让我想起了以前的一个段子，说是一个大牛去 Google 面试，结果因为不会翻二叉树面试被毙了。

This problem was inspired by this original tweet by Max Howell: 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.

什么？谷歌 90% 的人都在用这个大牛写的软件，但是大牛因为不会翻二叉树，就谷歌毙了！?

看来不管你多牛，去谷歌你还是得先会翻二叉树啊。这里我们一起看看怎么用 JS 翻个二叉树。

这里来个二叉树的结构，大家试着翻翻看 :smile:

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

翻过来应该是这样的：

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

---

思考思考再往下看：

好吧，估计大家都已经写好代码了。这里我也写了个很丑的代码供大家吐槽。

• 定义节点类

function TreeNode (val, left, right) {
  this.val = val
  this.left = left
  this.right = right
  return this
}

二叉树的左右节点用 left、right 表示。

• 生成原始二叉树

var node1 = new TreeNode(7, 9, 6)
var node2 = new TreeNode(2, 3, 1)
var root = new TreeNode(4, node1, node2)

root 就是上面的原始二叉树了，现在设计一个翻转函数。

var invertTree = function(root) {

    //遍历每个节点
    function loop (node) {
        var temp = null
        if (node && typeof node !== 'number') { //节点如果是节点对象则翻转左右节点
            temp = node.right 
            node.right = node.left
            node.left = temp
             //尝试继续翻转节点
            loop(node.left)
            loop(node.right)
        }
    }

    loop(root)

    return root
}

//执行翻转
invertTree(root)

结果如图：

突然间觉得人生大有可为了 :joy:

---

完整代码：

function TreeNode (val, left, right) {
  this.val = val
  this.left = left
  this.right = right
  return this
}

var invertTree = function(root) {

    //遍历每个节点
    function loop (node) {
        var temp = null
        if (node && typeof node !== 'number') { //节点如果是节点对象则翻转左右节点
            temp = node.right 
            node.right = node.left
            node.left = temp
             //尝试继续翻转节点
            loop(node.left)
            loop(node.right)
        }
    }

    loop(root)

    return root
}

var node1 = new TreeNode(7, 9, 6)
var node2 = new TreeNode(2, 3, 1)
var root = new TreeNode(4, node1, node2)

invertTree(root)

---

Thanks