每日第三题，今天的事情做完了，来刷道题爽一下

将有序数组转换为二叉搜索树

跳转链接

image-20211230212100152

解题思路

还是一样的，先确定二叉树的递归框架，二叉搜索树无非就是左子树小于根节点、右子树大于根节点，而满足高度平衡我们可以选择数组的中间元素作为根节点，这样左子树和右子树的就是高度平衡的。

说完这两个条件大家都应该明白了，我们需要选择数组的中间元素作为根节点，之后再选取小于根节点的数据做左子树，大于根节点的数据做右子树，这不就是前序遍历嘛！！！即我们最先确定根节点，再去遍历左右子树。

好了，书写递归最重要的一步我们确定了，接下来就可以确定递归的终止条件了，可以知道当数组为空的时候就没办法生成树了。所以终止条件就是数组为空

代码

func sortedArrayToBST(nums []int) *TreeNode {
	return sortedArrayToBSTHelper(nums, 0, len(nums)-1) // 这里使用了下标来标注一个数组的可访问范围
}

func sortedArrayToBSTHelper(nums []int, left, right int) *TreeNode {
	if len(nums) == 0 || left > right {
		return nil
	}

	var mid = (left + right) / 2

	var root = &TreeNode{Val: nums[(left + right) / 2]}

	root.Left = sortedArrayToBSTHelper(nums, left, mid-1) 
	root.Right = sortedArrayToBSTHelper(nums, mid+1, right)
	return root
}

写在最后

我们可是要成为卷王的男人QuQ