携手创作,一起成长!这是我参加「日新计划 8 月更文挑战」的第18天,点击检查活动详情

标题

给你一棵二叉树的根节点 root,翻转这棵二叉树,并返回其根节点。

说明: xxx

示例 1:

  • 输入:root = [4,2,7,1,3,6,9]
  • 输出:[4,7,2,9,6,3,1]

示例 2:

  • 输入:root = [2,1,3]
  • 输出:[2,3,1]

示例 3:

  • 输入:root = []
  • 输出:[]

办法一:递归

思路及解法

这是一道很经典的二叉树问题。显然,咱们从根节点开端,递归地对树进行遍历,并从叶子节点先开端翻转。如果当时遍历到的节点 rootroot 的左右两棵子树都已经翻转,那么咱们只需求交流两棵子树的位置,即可完成以 rootroot 为根节点的整棵子树的翻转。

代码

class Solution {
    func invertTree(_ root: TreeNode?) -> TreeNode? {
        if nil == root {
            return root
        }
        let left: TreeNode? = invertTree(root?.left)
        let right: TreeNode? = invertTree(root?.right)
        root?.left = right
        root?.right = left
        return root
    }
}

复杂度剖析

  • 时刻复杂度:O(N)O(N),其中 NN 为二叉树节点的数目。咱们会遍历二叉树中的每一个节点,对每个节点而言,咱们在常数时刻内交流其两棵子树。

  • 空间复杂度:O(N)O(N)。使用的空间由递归栈的深度决议,它等于当时节点在二叉树中的高度。在平均情况下,二叉树的高度与节点个数为对数联系,即 O(logN)O(logN)。而在最坏情况下,树构成链状,空间复杂度为 O(N)O(N)

办法二:迭代

思路及解法

递归实现也便是深度优先遍历的方法,那么对应的便是广度优先遍历。
广度优先遍历需求额定的数据结构–行列,来存放暂时遍历到的元素。
深度优先遍历的特点是一竿子插究竟,不行了再退回来继续;而广度优先遍历的特点是层层扫荡。
所以,咱们需求先将根节点放入到行列中,然后不断的迭代行列中的元素。
对当时元素互换其左右子树的位置,然后:

  • 判别其左子树是否为空,不为空就放入行列中
  • 判别其右子树是否为空,不为空就放入行列中

代码

class Solution {
    func invertTree(_ root: TreeNode?) -> TreeNode? {
        if nil == root {
            return root
        }
        var queue: [TreeNode?] = []
        queue.append(root)
        while !queue.isEmpty {
            let tmp: TreeNode? = queue.removeLast()
            let left: TreeNode? = tmp?.left
            tmp?.left = tmp?.right
            tmp?.right = left
            if tmp?.left != nil {
                queue.append(tmp?.left)
            }
            if tmp?.right != nil {
                queue.append(tmp?.right)
            }
        }
        return root
    }
}

复杂度剖析

  • 时刻复杂度:每个节点都需求入行列/出行列一次,所以是 O(n)O(n)

  • 空间复杂度:最坏的情况下会包含所有的叶子节点,彻底二叉树叶子节点是 n/2n/2 个,所以时刻复杂度是 O(n)O(n)