1382. 将二叉搜索树变平衡

先变为有序递增数组，再平衡

class Solution {
    var list: [Int] = []

    func balanceBST(_ root: TreeNode?) -> TreeNode? {
        getList(root)
        return buildTree(list, 0, list.count - 1)
    }

    func buildTree(_ nums: [Int], _ left: Int, _ right: Int) -> TreeNode? {
        if left > right {
            return nil
        }
        let mid = (left + right) / 2
        let root = TreeNode(nums[mid])
        root.left = buildTree(nums, left, mid - 1)
        root.right = buildTree(nums, mid + 1, right)
        return root
    }

// 二叉搜索树
//若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 
// 所以采用中序遍历  先左 再根 最后右  刚好是递增数组
    func getList(_ root: TreeNode?) {
        guard let root = root else { return }
        getList(root.left)
        list.append(root.val)
        getList(root.right)
    }
}