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