leetcode Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree

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

本题是二分法的高级应用，每次选择root都是从数列的中间选择，那么最后构造出来的二叉树一定是高度平衡的BST了。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution 
{
public:
	TreeNode *sortedArrayToBST(vector<int> &num) 
	{
		return biSortedArrayToBST(num, 0, num.size()-1);
	}

	TreeNode *biSortedArrayToBST(vector<int> &num, int low, int up)
	{
		if (low > up) return NULL;
		int mid = low + ((up-low)>>1);
		TreeNode *r = new TreeNode(num[mid]);

		r->left = biSortedArrayToBST(num, low, mid-1);
		r->right = biSortedArrayToBST(num, mid+1, up);

		return r;
	}
};

leetcode Convert Sorted Array to Binary Search Tree

原文：http://blog.csdn.net/kenden23/article/details/17590023