Problem

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example

Solution

题目要求将有序数组转化成一棵height-balanced的BST，容易想到从数组中间分成两半，分别作为左右子树。

/** * 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) { return sortedArrayToBST(nums,0,nums.size()-1); } TreeNode* sortedArrayToBST(vector<int>& nums,int l,int r) { if(l > r) return NULL; int mid = (l + r )/ 2; TreeNode *root = new TreeNode(nums[mid]); root->left = sortedArrayToBST(nums,l,mid-1); root->right = sortedArrayToBST(nums,mid+1,r); return root; } };