Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
解题思路:
递归做。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode *createTree(vector<int> &num, int start, int end) { if(start > end) return NULL; int mid = (start + end) / 2; TreeNode *l = createTree(num, start, mid - 1); TreeNode *r = createTree(num, mid + 1, end); TreeNode *cur = new TreeNode(num[mid]); cur -> left = l; cur -> right = r; return cur; } TreeNode *sortedArrayToBST(vector<int> &num) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. return createTree(num, 0, num.size() - 1); } };