携手创作，一起成长！这是我参加「日新计划 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 = []
• 输出：[]

办法一：递归

思路及解法

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

代码

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)$，其中 $N$ 为二叉树节点的数目。咱们会遍历二叉树中的每一个节点，对每个节点而言，咱们在常数时刻内交流其两棵子树。

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

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