力扣热题100 - 二叉树：将有序数组转换为二叉搜索树

题目描述：

题号：108

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

解题思路：

思路一：中序构建二叉树

1. 选择根节点：

   • 首先，选择数组的中间元素作为根节点。这样做可以确保生成的二叉搜索树尽可能平衡。

2. 递归构建子树：

   • 将数组分为左半部分和右半部分。左半部分包含所有小于根节点的元素，右半部分包含所有大于根节点的元素。

   • 对左半部分递归执行相同的过程，即选择中间元素作为左子树的根节点，并继续分割数组构建左子树的子树。

   • 对右半部分同样递归执行，选择中间元素作为右子树的根节点，并继续分割数组构建右子树的子树。

3. 保持平衡：

   • 在递归过程中，始终选择中间元素作为根节点，这样可以确保左右子树的高度差尽可能小，从而保持树的平衡。

时间复杂度：O(N)

空间复杂度：O(logN) 

C++

// C++
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    TreeNode* builder(vector<int>& nums, int left, int right) {
        if (left > right) {
            return nullptr;
        }

        int mid = (left + right) / 2;

        TreeNode* root = new TreeNode(nums[mid]);
        root->left = builder(nums, left, mid - 1);
        root->right = builder(nums, mid + 1, right);
        return root;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return builder(nums, 0, nums.size() - 1);
    }
};

go

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

func builder(nums []int, left, right int) *TreeNode {
    if left > right {
        return nil
    }
    mid := (left + right) / 2
    root := &TreeNode{Val: nums[mid]}
    root.Left = builder(nums, left, mid - 1)
    root.Right = builder(nums, mid + 1, right)
    return root
}