你能在白板上写出如何反转一棵二叉树吗？ |
您所在的位置：网站首页 › bigbang红霞mv宣传板上写了什么 › 你能在白板上写出如何反转一棵二叉树吗？ |
你能在白板上写出如何反转一棵二叉树吗？
|
技术招聘已经变味了： Homebrew 作者 Max Howell 面试谷歌被拒为例。谷歌说他们有 90% 的员工使用了 Max 开发的 Homebrew，但因为在面试时 Max 没能在白板上写出如何反转一颗二叉树而被拒。 题目描述  题解其实就是交换一下左右节点，然后再递归的交换左节点，右节点 根据动画图我们可以总结出递归的两个条件如下： 终止条件：当前节点为null时返回 交换当前节点的左右节点，再递归的交换当前节点的左节点，递归的交换当前节点的右节点 时间复杂度：每个元素都必须访问一次，所以是O(n) 空间复杂度：最坏的情况下，需要存放O(h)个函数调用(h是树的高度)，所以是O(h) 代码实现如下： 代码语言：javascript复制package i /** * @author: Jack * 2020-05-08 13:41 * 面试题27. 二叉树的镜像 请完成一个函数，输入一个二叉树，该函数输出它的镜像。 例如输入： 4 / \ 2 7 / \ / \ 1 3 6 9 镜像输出： 4 / \ 7 2 / \ / \ 9 6 3 1 示例 1： 输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1] */ fun mirrorTree(root: TreeNode?): TreeNode? { if (null == root) return null mirrorNode(root) mirrorTree(root.left) mirrorTree(root.right) return root } private fun mirrorNode(root: TreeNode) { val right = root.right root.right = root.left root.left = right } class TreeNode(var n: Int) { var left: TreeNode? = null var right: TreeNode? = null override fun toString(): String { return "TreeNode(n=$n, left=$left, right=$right)" } } fun main() { val root = TreeNode(4) val left = TreeNode(2) root.left = left left.left = TreeNode(1) left.right = TreeNode(3) val right = TreeNode(7) root.right = right right.left = TreeNode(6) right.right = TreeNode(9) println(root) mirrorTree(root) println(root) }运行输出： 代码语言：javascript复制TreeNode(n=4, left=TreeNode(n=2, left=TreeNode(n=1, left=null, right=null), right=TreeNode(n=3, left=null, right=null)), right=TreeNode(n=7, left=TreeNode(n=6, left=null, right=null), right=TreeNode(n=9, left=null, right=null))) TreeNode(n=4, left=TreeNode(n=7, left=TreeNode(n=9, left=null, right=null), right=TreeNode(n=6, left=null, right=null)), right=TreeNode(n=2, left=TreeNode(n=3, left=null, right=null), right=TreeNode(n=1, left=null, right=null)))OK，也许你写出来了反转二叉树的代码，但是你就是写不出来homebrew，这个世界太扯淡了…… |
【本文地址】
今日新闻 |
推荐新闻 |