《leetcode-go》将升序数组转化为平衡二叉搜索树

最新推荐文章于 2023-02-25 23:03:36 发布

less_cold

最新推荐文章于 2023-02-25 23:03:36 发布

阅读量206

点赞数

分类专栏： leetCode-go 文章标签： leetcode golang 算法

本文链接：https://blog.csdn.net/less_cold/article/details/120120192

版权

leetCode-go 专栏收录该内容

81 篇文章

订阅专栏

给出一个升序排序的数组，将其转化为平衡二叉搜索树（BST）.

思路：无非就是取中间作为根节点，然后左右两边递归调用即可

package main
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
  * 
  * @param num int整型一维数组 
  * @return TreeNode类
*/
func sortedArrayToBST( num []int ) *TreeNode {
    // write code here
    cnt := len(num)
	if cnt == 0 {
		return nil
	}
	if cnt == 1 {
		treeNode := new(TreeNode)
		treeNode.Val = num[0]
		return treeNode
	}
	mid := cnt / 2
	treeNode := new(TreeNode)
	treeNode.Val = num[mid]
	treeNode.Left = sortedArrayToBST(num[:mid])
	treeNode.Right = sortedArrayToBST(num[mid+1:])
	return treeNode
}