题目内容

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

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

示例

示例 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,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示

1、1 <= nums.length <= 10^4
2、-10^4 <= nums[i] <= 10^4
3、nums 按 严格递增 顺序排列

题解

本题在思路上，可以采用递归建立整棵二叉树的方式进行。因为要建立平衡的二叉搜索树，因此左右子树的高度差不大于1，这就要求左右子树的节点数量必须近乎相等，因此每次以中点作为根是必要的。然后，以左半边为左子树，右半边为右子树，递归建立左子树和右子树之后，令根节点指针分别指向左右子树即可。

有个结论大家记住就行了，这里不展开证明：利用上述方法构造出的二叉搜索树的高度为，这是满足形成一颗高度平衡的二叉搜索树的条件的。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return build(0, nums.size() - 1, nums);
    }

    TreeNode* build(int l, int r, vector<int>& nums)
    {
        if (l > r) return 0;//如果l大于r，达到递归的终止条件
        int mid = (l + r) / 2;//取中点，这里也可以写成 l+r >> 1
        TreeNode *root = new TreeNode(nums[mid]);//创建一个新的节点
        root->left = build(l, mid - 1, nums);//构造左子树
        root->right = build(mid + 1, r, nums);//构造右子树
        return root;
    }
};