这道题使用递归，可以简单到只需要五行代码。但是如果不用呢？我想了几乎一天，也没有什么特别体面的主意。（不是没办法，是太不优美了。）
BST 的概念倒是可以适当复习下，不得不说，这个东西在数据库以及检索系统中，有着非常广泛的应用。而这道题其实并没有考察它的什么特性，顶多算一道宽要求的逆向中序遍历罢了。貌似在我最近看的《编程之美》里面有提及。
今天是我写 LeetCode 系列的第 21 天，有些人可是用这样长的时间学会了C++呢。(笑
我很难花太多时间在这上面（最近给3D模型调光照超级闹心），貌似也越来越给自己降低要求了（以前无论如何也要想出非递归算法的）。和 @Mooophy 那种一边复习考试，一边还能刷完 1／3 的学霸无法相提并论。
我就是玩玩，放松吧。。。哈哈～
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
#include <vector>
#include <cstddef>
using std::vector;
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 sortedArrayToBST(num.begin(), num.end());
}
TreeNode *sortedArrayToBST(vector<int>::iterator beg, vector<int>::iterator end)
{
if (beg == end) return NULL;
auto mid = beg + (end - beg)/2;
TreeNode *root = new TreeNode(*mid);
root->left = sortedArrayToBST(beg, mid);
root->right = sortedArrayToBST(std::next(mid), end);
return root;
}
};