用递归呢不太好,这里就不写通过loop解决的方案了。思路也很简单,就是先将所有TreeNode的值按大小排序,然后赋值回原来的树结构。
先看递归思路

func preOrder(_ root: TreeNode?) -> [TreeNode] {
    guard let r = root else { return [] }
    return preOrder(r.left) + [r] + preOrder(r.right)
}
func recoverTree(_ root: TreeNode?) {
    let nodes = preOrder(root)
    let nodesSorted = nodes.map{ $0.val }.sorted()
    for i in 0..<nodes.count {
        nodes[i].val = nodesSorted[i]
    }
}

这里我用了Swift原生的sorted方法,我自己写了个quicksort效率没有这个高,我猜想是否因为测试用例的问题。
使用上面的方法,效率如下:
Runtime: 68 ms, faster than 100.00% of Swift online submissions for Recover Binary Search Tree.
Memory Usage: 19.6 MB, less than 33.33% of Swift online submissions for Recover Binary Search Tree.
下面是快速排序,上面的代码中我没用上:

func quickSort(_ list: [Int]) -> [Int] {
    guard !list.isEmpty else { return [] }
    let mid = list[list.count/2]
    return quickSort(list.filter{ $0 < mid })
        + [mid]
        + quickSort(list.filter{ $0 > mid })
}