這道算法源于一個故事
程序員 Howell 在 Google 面試時遇到了讓人悲傷的情境。他把這次面試經(jīng)歷寫成了一條簡短的推文： Google：我們 90% 的工程師都用你寫的軟件（Homebrew），但你沒法在白板上翻轉(zhuǎn)二叉樹，所以滾蛋吧。

那么我們今天看一下這道翻轉(zhuǎn)二叉樹

輸入:

      1
    /   \
  2      3
 / \    / \
4   5  6   7

返回:

      1
    /   \
  3      2
 / \    / \
5  4   7   6

即: 左右子節(jié)點(diǎn)互換

思路

思路很簡單, 遞歸調(diào)用自身方法
方法里面令 左子節(jié)點(diǎn)=右子節(jié)點(diǎn) 右子節(jié)點(diǎn)=左子節(jié)點(diǎn) 繼續(xù)遞歸

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func invertTree(_ root: TreeNode?) -> TreeNode? {
        if root == nil {
            return nil
        }
        let temp = root!.left
        root!.left = root!.right
        root!.right =  temp
        invertTree(root!.left)
        invertTree(root!.right)
        return root
    }
}

時間復(fù)雜度：
O(N), 其中 N 為二叉樹節(jié)點(diǎn)的數(shù)目。我們會遍歷二叉樹中的每一個節(jié)點(diǎn)，對每個節(jié)點(diǎn)而言，我們在常數(shù)時間內(nèi)交換其兩棵子樹。

空間復(fù)雜度：
O(N),使用的空間由遞歸棧的深度決定，它等于當(dāng)前節(jié)點(diǎn)在二叉樹中的高度。在平均情況下，二叉樹的高度與節(jié)點(diǎn)個數(shù)為對數(shù)關(guān)系，即 O(logN)。而在最壞情況下，樹形成鏈狀，空間復(fù)雜度為 O(N)

題目來源：力扣（LeetCode） 感謝力扣爸爸 :)
IOS 算法合集地址