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

• 108.将有序数组转换为二叉搜索树
  • 递归
  • 迭代

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedArrayToBST(nums []int) *TreeNode {
	size := len(nums)
	if size == 0 {
		return nil
	}
	mid := size >> 1
	node := &TreeNode{ Val: nums[mid] }
	node.Left = sortedArrayToBST(nums[:mid])
	node.Right = sortedArrayToBST(nums[mid + 1:])
	return node
}

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

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