美文网首页
109. Convert Sorted List to Bina

109. Convert Sorted List to Bina

作者: sarto | 来源:发表于2022-05-27 11:19 被阅读0次

    题目

    将一个升序排列的数组转换为一刻平衡的二叉搜索树

    解析

    二叉搜索树是左子树小于根节点,又子树大于根节点,那么对于一个单调递增数组来说,我们任意选择一个数,这个数组左侧是小于该节点的,右侧是大于该节点的。恰好符合二叉搜索树的结构,然后我们递归下去,即可得到一颗完整的二叉搜索树,为了保证高度平衡,选择中间节点,保证左右子树结构相同,节点相同,那么高度自然也相同。

    区别在于,这个题目给出了链表,比起直接数组切片访问,复杂了一些,将其转为数组。

    伪代码

    代码

    func sortedListToBST(head *ListNode) *TreeNode {
        nums := make([]int, 0)
        for head != nil {
            nums=append(nums, head.Val)
            head=head.Next
        }
        return tobst(nums)
    }
    
    func tobst(nums []int) *TreeNode {
        if len(nums) == 0 {
            return nil
        }
        k := len(nums) / 2
        node := &TreeNode{Val: nums[k]}
        node.Left = tobst(nums[:k])
        node.Right = tobst(nums[k+1:])
        return node
    }
    
    image.png

    相关文章

      网友评论

          本文标题:109. Convert Sorted List to Bina

          本文链接:https://www.haomeiwen.com/subject/unymprtx.html