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

  |   0 评论   |   0 浏览

题目

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

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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
}

image.png


标题:LeetCode-108-将有序数组转换为二叉搜索树
作者:guobingwei
地址:http://guobingwei.tech/articles/2020/10/25/1603560067062.html