LeetCode Q108: Convert Sorted Array to Binary Search Tree

 Given an array where elements are sorted in ascending order, convert it to a 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* helper(vector<int>& nums, int l, int r, int num){
	if(num==0)
	return NULL;
	int mid=l+(r-l+1)/2;
	TreeNode* node=new TreeNode(nums[mid]);
	int lnum=max(mid-l, 0);
	int rnum=max(r-mid, 0);
	TreeNode* lnode=helper(nums, l, mid-1, lnum);
	TreeNode* rnode=helper(nums, mid+1, r, rnum);
	node->left=lnode;
	node->right=rnode;
	return node;
	}
	TreeNode* sortedArrayToBST(vector<int>& nums) {
	TreeNode* root=helper(nums, 0, nums.size()-1, nums.size());
	return root;
	}
	};

view raw Q108ArraytoBST.cpp hosted with ❤ by GitHub