654. 最大二叉树

递归结束条件：nums中没有元素
明确函数的定义（但不跳进递归去）：找到最大值及最大值的索引，并根据索引将其分成左右两个子nums集合
左右子树递归调用该函数

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def constructMaximumBinaryTree(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if not nums: return None
        max_val=max(nums)
        max_index=nums.index(max_val)
        root=TreeNode(max_val)
        root.left=self.constructMaximumBinaryTree(nums[:max_index])
        root.right=self.constructMaximumBinaryTree(nums[max_index+1:])
        return root

//#include <bits/stdc++.h>
//using namespace std;
//
////Definition for a binary tree node.
//struct TreeNode {
//    int val;
//    TreeNode *left;
//    TreeNode *right;
//    TreeNode() : val(0), left(nullptr), right(nullptr) {}
//    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
//};

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if (nums.size() == 0) return nullptr;
//        最大值及其对应的索引
        vector<int>::iterator idx=max_element(nums.begin(), nums.end()); // 或者：auto idx=max_element(nums);
        int maxVal=*idx;
//        构建新的节点
        TreeNode* root=new TreeNode (maxVal);
//        递归调用最大值两边的左右两个子数组
        vector<int>l(nums.begin(),idx);
        vector<int>r(idx+1,nums.end());
        root->left= constructMaximumBinaryTree(l);
        root->right= constructMaximumBinaryTree(r);
        return root;
    }
};