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

目录

1.解题思路

2.代码块

3.自己的拙见

---

1.解题思路

BST的中序遍历是升序的，因此本题等同于根据中序遍历的序列恢复二叉搜索树。

因此我们可以以升序序列中的任一个元素作为根节点，以该元素右边的升序序列构建左子树，以该元素右边的升序序列构建右子树，这样得到的树就是一棵二叉搜索树啦～ 又因为本题要求高度平衡，因此我们需要选择升序序列的中间元素作为根节点。

2.代码块

/**
 * 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 {
public:
    TreeNode* sortedArrayToBST(vector& nums) {
        return helper(nums, 0, nums.size() - 1);
    }

    TreeNode* helper(vector& nums, int left, int right) {
        if (left > right) {
            return nullptr;
        }

        // 总是选择中间位置右边的数字作为根节点
        int mid = (left + right + 1) / 2;

        TreeNode* root = new TreeNode(nums[mid]);
        root->left = helper(nums, left, mid - 1);
        root->right = helper(nums, mid + 1, right);
        return root;
    }
};

3.自己的拙见

由于递归法是基于二分查找法，所以一定要选择中间位置右边的数字作为根节点，不然就会报错。

int mid = (left + right + 1) / 2;