题目描述#

给定一个整数数组 nums，元素已经按升序排列。要求把它转换成一棵 平衡 二叉搜索树（任意节点左右子树高度差不超过 1）。

由于答案不唯一，只要满足 BST 性质并且高度平衡即可。

思路#

升序数组其实就是 BST 的中序遍历结果。这就好办啦——既然中序遍历能唯一还原中序顺序，那么任意挑一个元素当根、左半边递归构造左子树、右半边递归构造右子树，得到的一定是合法的 BST。问题只剩下：怎么挑根才能让树高度平衡？

答案是 每次都挑当前区间的中点。这样左右两边的元素个数最多差 1，递归到底时左右子树的高度差自然就被控制在 1 以内，整棵树高度是 O(log n)。本姑娘就喜欢这种切一刀两边对称的感觉，分治嘛，就是要分得整整齐齐～

实现上写一个闭包 dfs(left, right)，含义是“用 nums[left..right] 构造一棵平衡 BST 并返回根节点”。

• 当 left > right 时，区间为空，返回 nil，对应叶子下面的空指针。
• 否则计算 mid = left + (right-left)/2，这种写法可以避免 left + right 直接相加在极端情况下溢出。
• 用 nums[mid] 建一个新节点，左孩子递归 dfs(left, mid-1)，右孩子递归 dfs(mid+1, right)。

整个过程每个元素只被访问一次，时间复杂度是 O(n)；递归栈深度等于树高 O(log n)，所以额外空间是 O(log n)，不计算返回的树本身。

思维边界#

• BST + 中序 = 升序：升序数组就是合法 BST 的中序遍历，所以从这个数组构造 BST 一定有解。
• 平衡的来源：取中点会保证左右子区间长度最多差 1，递归之后整棵树高度差不超过 1，符合“平衡”的定义。
• mid 的选择：取 (left+right)/2 还是 (left+right+1)/2 都行，前者偏左、后者偏右，都能得到平衡树，只是树长得不一样。
• 防溢出写法：mid := left + (right-left)/2 在工程里是更稳妥的习惯，本题区间不大其实不会溢出，但顺手写出来不亏。
• 递归终止：用 right < left 而不是 right <= left，因为 left == right 时区间里还有一个元素需要建节点。
• 空数组：nums 为空时 dfs(0, -1) 直接返回 nil，结果就是空树，不需要单独特判。

代码#

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedArrayToBST(nums []int) *TreeNode {
	var dfs func(left int, right int) *TreeNode
	dfs = func(left int, right int) *TreeNode {
		if right < left {
			return nil
		}
		mid := left + (right-left)/2
		return &TreeNode{
			Val:   nums[mid],
			Left:  dfs(left, mid-1),
			Right: dfs(mid+1, right),
		}
	}
	return dfs(0, len(nums)-1)
}