IOS 算法(基础篇) ----- 翻转二叉树

这道算法源于一个故事
程序员 Howell 在 Google 面试时遇到了让人悲伤的情境。他把这次面试经历写成了一条简短的推文： Google：我们 90% 的工程师都用你写的软件（Homebrew），但你没法在白板上翻转二叉树，所以滚蛋吧。

那么我们今天看一下这道翻转二叉树

输入:

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

返回:

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

即: 左右子节点互换

思路

思路很简单, 递归调用自身方法
方法里面令 左子节点=右子节点 右子节点=左子节点 继续递归

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

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

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

题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址