- 二叉搜索树的中序遍历就是升序排序的,因此题目实际就是根据中序遍历构建二叉搜索树。又因为要保持高度平衡,所以每次取中间元素为根节点,左侧元素为左子树,右侧元素为右子树即可
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return dfs(nums, 0, size(nums));
}
TreeNode* dfs(vector<int>& nums, int l, int r) {
if (l >= r) {
return nullptr;
}
int m = l + (r - l) / 2;
TreeNode* t = new TreeNode(nums[m]);
t->left = dfs(nums, l, m);
t->right = dfs(nums, m + 1, r);
return t;
}
};