leetcode 最大二叉树 -- 递归分治

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

• 二叉树的根是数组中的最大元素。
• 左子树是通过数组中最大值左边部分构造出的最大二叉树。
• 右子树是通过数组中最大值右边部分构造出的最大二叉树。

通过给定的数组构建最大二叉树，并且输出这个树的根节点。

示例：

输入：[3,2,1,6,0,5]
输出：返回下面这棵树的根节点：

     6
   /   \
  3     5
   \    / 
    2  0   
      \
       1

提示：

• 给定的数组的大小在 [1, 1000] 之间。

好久没看过树了，这道题完全没有思路，这是讨论区的思路。

递归套路三部曲：

• 找终止条件：当l>r时，说明数组中已经没元素了，自然当前返回的节点为null。
• 每一级递归返回的信息是什么：返回的应该是当前已经构造好了最大二叉树的root节点。
• 一次递归做了什么：找当前范围为[l,r]的数组中的最大值作为root节点，然后将数组划分成[l,bond-1]和[bond+1,r]两段，并分别构造成root的左右两棵子最大二叉树。

class Solution {
public:
    int findMax(vector<int>& nums, int l, int r){
        int maxIndex = l;
        for(int i=l+1;i<=r;i++){
            if(nums[i] > nums[maxIndex]){
                maxIndex = i;
            }
        }
        return maxIndex;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return maxTree(nums, 0, nums.size()-1);
    }
    TreeNode* maxTree(vector<int>& nums, int l, int r){
        if(l>r){
            return NULL;
        }
        int maxIndex = findMax(nums, l, r);
        TreeNode *root = new TreeNode(nums[maxIndex]);
        root->left = maxTree(nums, l, maxIndex-1);
        root->right = maxTree(nums, maxIndex+1, r);
        return root;
    }
};

题目链接：https://leetcode-cn.com/problems/maximum-binary-tree/