226. 翻转二叉树 - 简单

226. 翻转二叉树

迭代解法

• 时间复杂度
  O(n) n 为节点个数，每个节点访问一次
• 空间复杂度
  O(n)

// 从根节点开始反转的
    func invertTree2(_ root: TreeNode?) -> TreeNode? {
        guard let root = root else { return nil }

        var treeRoot = root
        let ansRoot = root
        var list: [TreeNode] = [treeRoot]
        while !list.isEmpty {
            treeRoot = list.popLast()!
            let temp = treeRoot.right
            treeRoot.right = treeRoot.left
            treeRoot.left = temp
            if treeRoot.left != nil {
                list.append(treeRoot.left!)
            }
            if treeRoot.right != nil {
                list.append(treeRoot.right!)
            }
        }

        return ansRoot
    }

递归解法

• 时间复杂度
  O(n) n 为节点个数，每个节点访问一次
• 空间复杂度
  O(n)

// 从叶子节点开始反转的
    func invertTree(_ root: TreeNode?) -> TreeNode? {
        guard let root = root else { return nil }
        let left = invertTree(root.left)
        let right = invertTree(root.right)
        root.left = right
        root.right = left
        return root
    }