Convert Sorted Array to Binary Search Tree [LeetCode]
5815 ワード
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
Summary: pretty easy, recursive staff.
Summary: pretty easy, recursive staff.
1 class Solution {
2 public:
3 TreeNode *sortedArrayToBST(vector<int> &num) {
4 int size = num.size();
5 if(size == 0)
6 return NULL;
7 if(size == 1)
8 return new TreeNode(num[0]);
9 if(num.size() % 2 == 1) {
10 TreeNode * root = new TreeNode(num[size/2]);
11 if(size/2 - 1 >= 0){
12 vector<int> left(num.begin(), num.begin() + size/2);
13 root->left = sortedArrayToBST(left);
14 }
15 if(size/2 + 1 < size) {
16 vector<int> right(num.begin() + size/2 + 1, num.end());
17 root->right = sortedArrayToBST(right);
18 }
19 return root;
20 }else {
21 TreeNode * root = new TreeNode(num[size/2 - 1]);
22 if(size/2 - 1 - 1 >= 0){
23 vector<int> left(num.begin(), num.begin() + size/2 - 1);
24 root->left = sortedArrayToBST(left);
25 }
26 if(size/2 - 1 + 1 < size) {
27 vector<int> right(num.begin() + size/2 -1 + 1, num.end());
28 root->right = sortedArrayToBST(right);
29 }
30 return root;
31 }
32 }
33 };