思路：

找到 vector 中的最大值的“指针”，用来构建当前节点，然后左子树用 最大值 左边构造，右子树用 最大值 右边构造。

递归基：当 vector 长度为0时即可返回。

AC代码(ps.这个递归方法速度又慢，占用内存又大...可能是传参重新创建了vector的缘故？)

 1 void Create(vector<int> nums, TreeNode *&root)
 2     {
 3         if (nums.size() == 0)
 4             return;
 5         vector<int>::iterator n = max_element(nums.begin(), nums.end());
 6         root = new TreeNode;
 7         root->val = *n;
 8         root->left = nullptr;
 9         root->right = nullptr;
10         Create(vector<int>(nums.begin(), n), root->left);
11         Create(vector<int>(n + 1, nums.end()), root->right);
12     }
13     TreeNode *constructMaximumBinaryTree(vector<int> &nums)
14     {
15         TreeNode *ans = nullptr;
16         if (nums.size() == 0)
17             return ans;
18         Create(nums, ans);
19         return ans;
20     }

 

 

哈哈哈，果然是重新构造vector耗时间，直接用迭代器传参，速度直接快了～

代码：

 1 void Create(vector<int>::iterator from, vector<int>::iterator to, TreeNode *&root)
 2     {
 3         if (from == to)
 4             return;
 5         vector<int>::iterator n = max_element(from, to);
 6         root = new TreeNode;
 7         root->val = *n;
 8         root->left = nullptr;
 9         root->right = nullptr;
10         Create(from, n, root->left);
11         Create(n + 1, to, root->right);
12     }
13     TreeNode *constructMaximumBinaryTree(vector<int> &nums)
14     {
15         TreeNode *ans = nullptr;
16         if (nums.size() == 0)
17             return ans;
18         Create(nums.begin(), nums.end(), ans);
19         return ans;
20     }