Convert Sorted Array to Binary Search Tree

問題描述：將一個按照升序排列的有序數(shù)組，轉(zhuǎn)換為一棵高度平衡二叉搜索樹。

問題解決：題目要求是要將一個按照升序排列的有序數(shù)組轉(zhuǎn)換為一棵高度平衡的二叉搜索樹，二叉搜索樹我們知道，就是節(jié)點的值小于其右子樹節(jié)點的值而大于其左子樹節(jié)點的值，平衡則為該樹的任意節(jié)點左右子樹的高度差不超過一。因為數(shù)組已經(jīng)是按照升序排列好了的，所以很明顯，如果每次找出數(shù)組中間的值作為根節(jié)點，那么左邊的數(shù)組為根節(jié)點的左子樹，右邊的數(shù)組為根節(jié)點右子樹，然后再繼續(xù)劃分數(shù)組。到這里可以很清楚地知道我們可以使用遞歸來解決這個問題。

class Solution { public:TreeNode* sortedArrayToBST(vector<int>& nums) {int len=nums.size();if(len==0) return NULL;TreeNode *root=new TreeNode(nums[len/2]);vector<int> left,right;//左邊數(shù)組left.insert(left.begin(),nums.begin(),nums.begin()+len/2);//右邊數(shù)組right.insert(right.begin(),nums.begin()+len/2+1,nums.end());root->left=sortedArrayToBST(left);root->right=sortedArrayToBST(right);return root;} };

總結(jié)

以上是生活随笔為你收集整理的Leetcode Problem108的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。