108. Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
解题思路： int mid = (begin + end) / 2;
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* sortedArrayToBST(vector<int>& nums) { TreeNode* root =NULL; if(nums.size() == 0) return NULL; BSTreeCons(nums, 0, nums.size() - 1, root); return root; } void BSTreeCons(vector<int>& nums, int begin, int end, TreeNode*& root){ if(begin > end) return; int mid = (begin + end) / 2; root = new TreeNode(nums[mid]); BSTreeCons(nums, begin, mid - 1, root -> left); BSTreeCons(nums, mid + 1, end, root -> right); } };
结果如下：
