[Leetcode]Convert Sorted Array to Binary Search Tree

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

分治是比较好而且容易想到的思路。

1 class Solution { 2 public: 3 TreeNode *mergeAToT(vector<int> &num,int left,int right){ 4 if(left>right) 5 return NULL; 6 int mid = (right+left)/2; 7 TreeNode *node = new TreeNode(num[mid]); 8 node->left = mergeAToT(num,left,mid-1); 9 node->right = mergeAToT(num,mid+1,right); 10 return node; 11 } 12 TreeNode *sortedArrayToBST(vector<int> &num) { 13 return mergeAToT(num,0,num.size()-1); 14 } 15 };

 

转载于:https://www.cnblogs.com/desp/p/4340748.html