题目链接

题目描述：

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树，并且输出这个树的根节点。

示例 ：

654最大二叉树 - 图1

解题思路

  看了题目的要求，我闻到了浓浓的分治思想，通过最大值索引区分左右子树区间，分治到底～其实也没那么高大上，实际就是套用先序遍历框架递归建树，分治的思想都交给递归去做了。我们主要针对于当前结点的操作，即找到在[left...right]中nums的最大值，然后new一下建立结点就好啦。

代码

  1. class Solution {
  2. public:
  3.     TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
  4.         if(nums.size() == 0)
  5.             return NULL;
  7.         return helper(nums, 0, nums.size() - 1);
  8.     }
  10. private:
  11.     TreeNode* helper(vector<int>& nums, int left, int right){
  12.         if(left > right)
  13.             return NULL;
  15.         int index = getMaxIndex(nums, left, right);
  16.         TreeNode* root = new TreeNode(nums[index]);
  18.         root->left = helper(nums, left, index - 1);
  19.         root->right = helper(nums, index + 1, right);
  20.         return root;
  21.     }
  23.     int getMaxIndex(vector<int>& nums, int left, int right){
  24.         int result = -1, index = -1;
  25.         for(int i = left; i <= right; i++){
  26.             if(nums[i] > result){
  27.                 result = nums[i];
  28.                 index = i;
  29.             }
  30.         }
  31.         return index;
  32.     }
  33. };

如果有错误或者不严谨的地方，请务必给予指正，十分感谢。