leetcode 108.将有序数组转换为二叉搜索树

问题描述

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

二叉搜索树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按 严格递增 顺序排列

核心思路

寻找分割点，分割点作为当前节点，然后递归左区间和右区间。

分割点就是数组中间位置的节点。

如果数组长度为偶数，中间节点有两个，取哪一个都可以，只不过构成了不同的平衡二叉搜索树。

code

int mid = left + ((right - left) / 2);的写法相当于是如果数组长度为偶数，中间位置有两个元素，取靠左边的。

在调用traversal的时候传入的left和right分别是0和nums.size() - 1，因为定义的区间为左闭右闭。

class Solution {
private:
    TreeNode* traversal(vector<int>& nums, int left, int right) {
        if (left > right) return nullptr;
        int mid = left + ((right - left) / 2);
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = traversal(nums, left, mid - 1);
        root->right = traversal(nums, mid + 1, right);
        return root;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root = traversal(nums, 0, nums.size() - 1);
        return root;
    }
};