EEPW论坛

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

思路：和链表转化成平衡二叉树的思路一样，不过数组找中间位置比较简单

1. class Solution {  

2. public:  

3.     TreeNode* sortedArrayToBST(vector<int>& num)  

4.     {  

5.         if (num.empty())  

6.         {  

7.             return NULL;  

8.         }  

9.   

10.         return vecToBST(0, num.size()-1, num);  

11.     }  

12.   

13.     TreeNode* vecToBST(int low, int high, vector<int> v)  

14.     {  

15.         int mid;  

16.         mid = (low+high+1)/2;//找中间位置  

17.         TreeNode* root = new TreeNode(v[mid]);  

18.         if (mid-1>=low)  

19.         {  

20.             root->left= vecToBST(low, mid-1, v);  

21.         }  

22.         if (mid+1<=high)  

23.         {  

24.             root->right = vecToBST(mid+1, high, v);  

25.         }  

26.   

27.         return root;  

28.     }  

29. };