leetcode-invert-binary-tree

蚊子前端博客
发布于 2015-06-17 06:00
使用JavaScript解决反转二叉树的问题

最近的一个新闻倒是挺火的,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):

leetcode-invert-binary-tree-蚊子的前端博客

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

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

COPYJAVASCRIPT

/** * 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; };

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

标签:
阅读(474)

公众号:

qrcode

微信公众号:前端小茶馆