## 108. Convert Sorted Array to Binary Search Tree 原

cofama

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;
}
};
``````

### cofama

Leetcode 108. Convert Sorted Array to Binary Search Tree

xgnming
08/28
0
0
LeetCode Question Difficulty Distribution 问题难度和频率分布

Leetcode问题难度和频率分布表 引用自： https://zephyrusara.blogspot.jp/2014/07/leetcode-question-difficulty.html LeetCode Question Difficulty Distribution : Sheet1......

xidiancoder
2017/09/10
0
0

qq_32690999
01/25
0
0

2017/08/11
0
0

Abstract This chapter presents a survey of the various structures (techniques) that can be used in building inverted files, and gives the details for producing an inverted file ......

GarfieldEr007
2016/01/07
0
0

RestClientUtil和ConfigRestClientUtil区别说明

RestClientUtil directly executes the DSL defined in the code. ConfigRestClientUtil gets the DSL defined in the configuration file by the DSL name and executes it. RestClientUtil......

bboss
48分钟前
6
0

2
0
Linux系统设置全局的默认网络代理

9
0
java框架学习日志-6（bean作用域和自动装配）

8
0

kitty1116

7
0