TechNomads

题目

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

解法

因为左右高度不能大于1，所以可以找个中间节点，保证二叉树的平衡性。找到中间节点作为根节点，然后用递归遍历。另外需要注意的是，求中点不要用 int mid = (begin + end)/2，有溢出风险，稳妥的方法是 int mid = begin + (end-begin)/2。

go代码实现：

func sortedArrayToBST(nums []int) *TreeNode {

	return bst(nums, 0, len(nums)-1)
}

func bst(nums []int, begin int, end int) *TreeNode {
	if begin > end {
		return nil
	}

	var node = &TreeNode{}

	// 根节点
	mid := begin + (end-begin) / 2
	node.Val = nums[mid]
	node.Left = bst(nums, begin, mid-1)
	node.Right = bst(nums, mid+1, end)

	return node
}