LeetCode 108. 将有序数组转换为二叉搜索树Golang版

LeetCode 108. 将有序数组转换为二叉搜索树Golang版

1. 问题描述

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

2. 思路

2.1. 递归

构造二叉树的本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。

3. 代码

3.1. 递归代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedArrayToBST(nums []int) *TreeNode {
    return traversal(nums, 0, len(nums)-1)
}

func traversal(nums []int, left int, right int) *TreeNode {
    if left > right {
        return nil
    }

    // 找到分割点
    mid := left + (right - left) / 2

    root := &TreeNode {
        Val : nums[mid],
        Left : nil,
        Right : nil,
    }

    // 递归左区间和右区间
    root.Left = traversal(nums, left, mid - 1)
    root.Right = traversal(nums, mid + 1, right)
    return root
}

3.2. 另一种写法

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

    mid := len(nums) / 2
    
    node := &TreeNode {
        Val : nums[mid],
        Left : nil,
        Right : nil,
    }
    // fmt.Println(node.Val)
    node.Left = sortedArrayToBST(nums[:mid])
    node.Right = sortedArrayToBST(nums[mid+1:])
    return node
}