专栏首页皮皮瞎学编程Tree - 108. Convert Sorted Array to Binary Search Tree Easy

Tree - 108. Convert Sorted Array to Binary Search Tree Easy

108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

思路:

将有序数组变成bst,做法就是取出数组中的中位数当root节点,然后将root节点两边分别递归求bst,注意这里的中位数,如果是偶数个数组是向上取整,即[0, 1, 7, 8]的root是7,下标为2。

代码:

go:

/**

 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedArrayToBST(nums []int) *TreeNode {
    if nums == nil || len(nums) == 0 {
        return nil
    }
    
    return recursion(nums, 0, len(nums))
}

func recursion(nums []int, low int, high int) *TreeNode {
	if low >= high { // leaf
		return nil
	}

	mid := (high-low)/2 + low

	return &TreeNode{
		Val:   nums[mid],
		Left:  recursion(nums, low, mid),
		Right: recursion(nums, mid+1, high)}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Array - 16. 3Sum Closest

    Given an array nums of n integers and an integer target, find three integers in ...

    用户5705150
  • Array - 15. 3Sum

    Given an array nums of n integers, are there elements a, b, c in nums such that ...

    用户5705150
  • Array - 508. Wiggle Sort

    Given an unsorted array nums, reorder it in-place such that

    用户5705150
  • LeetCode - 存在重复元素

    原题地址:https://leetcode-cn.com/problems/contains-duplicate/

    晓痴
  • 单调栈-LeetCode 739、287(单调栈,桶计数)

    根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。 例如,给定...

    算法工程师之路
  • LWC 54:698. Partition to K Equal Sum Subsets

    LWC 54:698. Partition to K Equal Sum Subsets 传送门:698. Partition to K Equal Sum S...

    用户1147447
  • LeetCode第53题

    Given an integer array nums, find the contiguous subarray (containing at least o...

    用户3112896
  • LeetCode 666. 路径和 IV(树的遍历)

    给定一个包含三位整数的升序数组,表示一棵深度小于 5 的二叉树, 请你返回从根到所有叶子结点的路径之和。

    Michael阿明
  • LeetCode第七天

    ==数组 Medium== 40.(162)Find Peak Element ? JAVA //斜率思想,二分法 class Solution { p...

    郭耀华
  • 219. Contains Duplicate II

    Given an array of integers and an integer k, find out whether there are two dist...

    luozhiyun

扫码关注云+社区

领取腾讯云代金券