108. Convert Sorted Array to Binary Search Tree
108. Convert Sorted Array to Binary Search Tree
cofama 发表于12个月前
108. Convert Sorted Array to Binary Search Tree
• 发表于 12个月前
• 阅读 1
• 收藏 0
• 评论 0

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

``````/**
* 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) {
int n = nums.size();
if(n==0) return NULL;

vector<TreeNode*> nodeList;
vector<TreeNode*>::iterator it;
int mid = n/2;
int lb, ub, leftIndex, rightIndex;

TreeNode* root = new TreeNode(mid);
TreeNode* cur;
nodeList.push_back(root);
int i = 0;

while(i<n) {
cur = nodeList[i];
lb = 0;
ub = n-1;
if(cur->right != NULL) {
ub = cur->right->val-1;
}
if(cur->left != NULL) {
lb = cur->left->val+1;
}

mid = cur->val;
leftIndex = (mid+lb)/2;
rightIndex = (mid+ub+2)/2;

if(leftIndex<mid && leftIndex>=lb) {
TreeNode* left = new TreeNode(leftIndex);
left->right = cur;
left->left = cur->left;
cur->left = left;
nodeList.push_back(cur->left);
}
else cur->left = NULL;
if(rightIndex>mid && rightIndex<=ub) {
TreeNode* right = new TreeNode(rightIndex);
right->left = cur;
right->right = cur->right;
cur->right = right;
nodeList.push_back(cur->right);
}
else cur->right = NULL;

++i;
}

for(it=nodeList.begin(); it!=nodeList.end(); ++it) {
cur = *it;
cur->val = nums[cur->val];
}
return root;
}
};
``````

×