題目

給定一個不含重復元素的整數數組。一個以此數組構建的最大二叉樹定義如下：

二叉樹的根是數組中的最大元素。
左子樹是通過數組中最大值左邊部分構造出的最大二叉樹。
右子樹是通過數組中最大值右邊部分構造出的最大二叉樹。
通過給定的數組構建最大二叉樹，并且輸出這個樹的根節點。

思路和之前的構造樹一樣：分成左右區間（子樹）遞歸

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* traversal (vector<int>& nums, int numsBegin, int numsEnd) {if (numsBegin == numsEnd) return NULL;//尋找最大數值int maxVal = nums[numsBegin];int delimiterIndex=numsBegin;for(int i=numsBegin;i<numsEnd;i++){if(nums[i]>maxVal){delimiterIndex = i;maxVal=nums[delimiterIndex];}}TreeNode* root = new TreeNode(maxVal);//如果是葉子結點，返回結點if (numsEnd - numsBegin == 1) return root;// for (delimiterIndex = numsBegin; delimiterIndex < numsEnd; delimiterIndex++) {//     if (nums[delimiterIndex] == rootValue) break;// }// 切割nums數組// 左區間，左閉右開[leftInorderBegin, leftInorderEnd)int leftorderBegin = numsBegin;int leftorderEnd = delimiterIndex;// 右區間，左閉右開[rightInorderBegin, rightInorderEnd)int rightorderBegin = delimiterIndex + 1;int rightorderEnd = numsEnd;root->left = traversal(nums, leftorderBegin, leftorderEnd);root->right = traversal(nums, rightorderBegin, rightorderEnd);return root;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {if(nums.size() == 0) return NULL;return traversal(nums,0,nums.size());}
};