leetcode-invert-binary-tree

最近的一个新闻倒是挺火的，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.（谷歌：虽然我们 90% 工程师都在用你写的软件（Homebrew），但你不能在白板上反转二叉树，所以滚蛋。）

现在让我们来亲自解一下这个面试题：如何反转二叉树。我们先来看看leetcode上对这个题目的具体描述（Invert Binary Tree）：

其实思路还是比较简单的：将当前的root节点的左右分支进行对调反转，若左分支存在，则将左分支的节点作为root节点进行对调反转；若右分支存在，则将右分支的节点作为root节点进行对调反转；一直**递归**到所有节点的左右分支都不存在。

这里使用js来解决这个反转二叉树的问题：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    // 传入的根节点可能就是null或者异常节点，则对root进行判断
    if(root){
        var temp = null;

        // 将当前节点的左右分支进行对调反转
        temp = root.left;
        root.left = root.right;
        root.right = temp;

        // 若左分支存在，则递归左分支的节点
        if(root.left){
            invertTree(root.left);
        }
        // 若右分支存在，则递归右分支的节点
        if(root.right){
            invertTree(root.right);
        }
    }
    // 所有的节点遍历完成后，返回根节点
    return root;
};

从以上的代码我们能够看出，算法其实还是比较简单的，递归其左右分支就能把整个二叉树进行反转。