1382. 将二叉搜索树变平衡

1382. 将二叉搜索树变平衡

二叉树 -> 数组 -> 平衡二叉树

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func balanceBST(root *TreeNode) *TreeNode {
    slice := toSlice(root)
    return toTree(slice)
}
 
func toSlice(root *TreeNode) []int {
    if root == nil {
        return nil
    }
    left := append(toSlice(root.Left), root.Val)
    return append(left, toSlice(root.Right)...)
}
 
func toTree(slice []int) *TreeNode {
    if len(slice) == 0 {
        return nil
    }
 
    mid := len(slice) / 2
    return &TreeNode {
        Val: slice[mid],
        Left: toTree(slice[:mid]),
        Right: toTree(slice[mid + 1:]),
    }
}