【算法题】将升序数组转化为平衡二叉搜索树

这题说的是把升序数组转化为二叉搜索树，所谓的二叉搜索树就是左子节点都比根节点值小，右子节点都比根节点值大，并且每一颗子树也都满足这个条件。

因为题中已经说了是有序数组，我们每次只需要取数组中间的值创建一个节点 node ，中间值左边的是 node 的左子节点，右边的是 node 的右子节点，node 的左右子树可以使用递归的方式继续创建，步骤如下图所示：

    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0)
            return null;
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }

    // 闭区间，start表示数组开始的位置，end表示的结束的位置
    public TreeNode sortedArrayToBST(int[] num, int start, int end) {
        if (start > end)// 空区间
            return null;
        int mid = (start + end) >> 1; // 中间节点
        // 取中间值作为当前节点
        TreeNode node = new TreeNode(num[mid]);
        // 然后递归的方式，中间值之前的是当前节点左子树的所有节点
        node.left = sortedArrayToBST(num, start, mid - 1);
        // 中间值之后的是当前节点的右子树的所有节点
        node.right = sortedArrayToBST(num, mid + 1, end);
        return node;
    }

public:
    TreeNode *sortedArrayToBST(vector<int> &nums) {
        if (nums.empty())
            return nullptr;
        return sortedArrayToBST(nums, 0, nums.size() - 1);
    }

    // 闭区间，start表示数组开始的位置，end表示的结束的位置
    TreeNode *sortedArrayToBST(vector<int> &nums, int start, int end) {
        if (start > end)
            return nullptr;
        int mid = (start + end) >> 1; // 中间节点
        // 取中间值作为当前节点
        auto *node = new TreeNode(nums[mid]);
        // 然后递归的方式，中间值之前的是当前节点左子树的所有节点
        node->left = sortedArrayToBST(nums, start, mid - 1);
        // 中间值之后的是当前节点的右子树的所有节点
        node->right = sortedArrayToBST(nums, mid + 1, end);
        return node;
    }

各大厂算法面试题已经整理好了，请看这里：《算法专栏》