Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
思路就是由于是排序，所以用二分法，左右子树递归生成。一开始我的代码会出现running time error。代码如下：
/** * 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 { TreeNode* BST(vector<int>& nums, int l,int r) { if(r<=l) return NULL; int mid=(r+l)/2; TreeNode* root = new TreeNode(nums[mid]); root->left=BST(nums,l,mid); root->right=BST(nums,mid,r); return root; } public: TreeNode* sortedArrayToBST(vector<int>& nums) { return BST(nums,0,nums.size()); } };
我实在想不到会是什么原因，细心检查一下原来是在递归右子树的时候，mid忘了+1；
AC：
/** * 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 { TreeNode* BST(vector<int>& nums, int l,int r) { if(r<=l) return NULL; int mid=(r+l)/2; TreeNode* root = new TreeNode(nums[mid]); root->left=BST(nums,l,mid); root->right=BST(nums,mid+1,r); return root; } public: TreeNode* sortedArrayToBST(vector<int>& nums) { return BST(nums,0,nums.size()); } };
