代码随想录算法【Day21】
Day21
108.将有序数组转换为二叉搜索树
递归法
思路有点类似二分法
class Solution {
private:
TreeNode* traversal(vector<int>& nums, int left, int right){
if(left > right) return nullptr;
int mid = left + ((right - left) / 2);
TreeNode* root = new TreeNode(nums[mid]);
root -> left = traversal(nums, left, mid - 1);
root -> right = traversal(nums, mid + 1 ,right);
return root;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
TreeNode* root = traversal(nums, 0, nums.size() - 1);
return root;
}
};
以下是模拟过程：
