108. 将有序数组转换为二叉搜索树
代码随想录
题目：
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
递归思路：
创建当前节点，然后调用递归函数，创建左树，创建右树。
递归代码：
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;
}
};
迭代法思路：
放个空节点，先建立关系，确定位置，再来给节点添值。
首先建立一个空节点，确定这个空节点应该在的位置，然后用两个队列一个存储这个空节点的start，一个存储这个空节点的end，然后进入循环，通过start，和end确定这个空节点的值，同时创建其左孩子节点和右孩子节点，与前面相似的操作，通过下一次的循环对空节点赋值。
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
queue<TreeNode*>t;
queue<int>left;
queue<int>right;
TreeNode* node = new TreeNode(0);
t.push(node);
left.push(0);
right.push(nums.size()-1);
while(!t.empty()){
TreeNode* prenode = t.front(); t.pop();
int preleft = left.front(); left.pop();
int preright = right.front();right.pop();
int mid = preleft+(preright-preleft)/2;
prenode->val = nums[mid];
if(preleft<=mid-1){
prenode->left = new TreeNode(0);
t.push(prenode->left);
left.push(preleft);
right.push(mid-1);
}
if(preright>=mid+1){
prenode->right = new TreeNode(0);
t.push(prenode->right);
left.push(mid+1);
right.push(preright);
}
}
return node;
}
};
