你能在白板上写出如何反转一棵二叉树吗？

一个会写诗的程序员

发布于 2020-05-18 15:19:36

5210

发布于 2020-05-18 15:19:36

文章被收录于专栏：一个会写诗的程序员的博客一个会写诗的程序员的博客

技术招聘已经变味了： 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，这个世界太扯淡了……

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法