技术招聘已经变味了： Homebrew 作者 Max Howell 面试谷歌被拒为例。谷歌说他们有 90% 的员工使用了 Max 开发的 Homebrew，但因为在面试时 Max 没能在白板上写出如何反转一颗二叉树而被拒。
题目描述
题解
其实就是交换一下左右节点，然后再递归的交换左节点，右节点
根据动画图我们可以总结出递归的两个条件如下：
终止条件：当前节点为null时返回
交换当前节点的左右节点，再递归的交换当前节点的左节点，递归的交换当前节点的右节点
时间复杂度：每个元素都必须访问一次，所以是O(n)
空间复杂度：最坏的情况下，需要存放O(h)个函数调用(h是树的高度)，所以是O(h)
代码实现如下：
-
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)
-
-
}
运行输出：
-
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，这个世界太扯淡了……
Kotlin开发者社区
专注分享 Java、 Kotlin、Spring/Spring Boot、MySQL、redis、neo4j、NoSQL、Android、JavaScript、React、Node、函数式编程、编程思想、"高可用，高性能，高实时"大型分布式系统架构设计主题。