题目

给你一棵二叉树的根节点 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 = []
• 输出：[]

方法一：递归

思路及解法

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

代码

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
    }
}

复杂度分析

• 时间复杂度：，其中 为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。

• 空间复杂度：。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 。而在最坏情况下，树形成链状，空间复杂度为 。

方法二：迭代

思路及解法

递归实现也就是深度优先遍历的方式，那么对应的就是广度优先遍历。
广度优先遍历需要额外的数据结构--队列，来存放临时遍历到的元素。
深度优先遍历的特点是一竿子插到底，不行了再退回来继续；而广度优先遍历的特点是层层扫荡。
所以，我们需要先将根节点放入到队列中，然后不断的迭代队列中的元素。
对当前元素调换其左右子树的位置，然后：

• 判断其左子树是否为空，不为空就放入队列中
• 判断其右子树是否为空，不为空就放入队列中

代码

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
    }
}

复杂度分析

• 时间复杂度：每个节点都需要入队列/出队列一次，所以是

• 空间复杂度：最坏的情况下会包含所有的叶子节点，完全二叉树叶子节点是 个，所以时间复杂度是