题解 | #将升序数组转化为平衡二叉搜索树#

package main
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
  * 
  * @param num int整型一维数组 
  * @return TreeNode类
*/
func sortedArrayToBST( num []int ) *TreeNode {
    // write code here
    // 选择中间的元素当做我们的头结点, 然后递归的将子数组全部变成BST
    // 递归 + 二分
    if len(num) == 0 {
        return nil
    }
    if len(num) == 1 {
        return &TreeNode{num[0], nil, nil}
    }
    left, right := 0, len(num)-1
    mid := right/2 + left/2
    root := &TreeNode{num[mid] ,nil, nil}
    root.Left = sortedArrayToBST(num[:mid])
    root.Right = sortedArrayToBST(num[mid+1:])
    return root
}