[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.

思考：

简单秒杀题。要BST平衡，自然要使每个节点的左右子树的大小尽可能接近。队列已经排序过，所以很自然可以取中间的数字为根节点。左半队列 < 中间数字 < 右边队列，符合BST的条件。然后分制递归来构建左右子树。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public: TreeNode *sortedArrayToBST(vector<int> &num) { return arrayToBST(num, 0, num.size()-1); } TreeNode *arrayToBST(vector<int> &num, int start, int end) { if(start>end) return NULL; int mid = start + (end-start)/2; TreeNode *root = new TreeNode(num[mid]); root->left = arrayToBST(num, start, mid-1); root->right = arrayToBST(num, mid+1, end); return root; } };