class Solution {
public:
// 如果不引用的话会重复copy内存空间 导致程序性能下降
// 引用保证在同一个地址操作
TreeNode* traversal(std::vector<int>& nums, int left, int right){
if (left > right) return nullptr;
int mid = (left + right) / 2;
TreeNode*root = new TreeNode(nums[mid]);
// 这个数组下标构造的根节点返回给当前根节点的左子树
root->left = traversal(nums, left, mid - 1);
root->right = traversal(nums, mid + 1, right);
return root;
}
TreeNode* sortedArrayToBST(std::vector<int>& nums) {
return traversal(nums, 0, nums.size()-1);
}
};