給定一個(gè)不含重復(fù)元素的整數(shù)數(shù)組。一個(gè)以此數(shù)組構(gòu)建的最大二叉樹(shù)定義如下：
- 二叉樹(shù)的根是數(shù)組中的最大元素憔披。
- 左子樹(shù)是通過(guò)數(shù)組中最大值左邊部分構(gòu)造出的最大二叉樹(shù)。
- 右子樹(shù)是通過(guò)數(shù)組中最大值右邊部分構(gòu)造出的最大二叉樹(shù)爸吮。
通過(guò)給定的數(shù)組構(gòu)建最大二叉樹(shù)芬膝，并且輸出這個(gè)樹(shù)的根節(jié)點(diǎn)。
示例：
輸入：[3,2,1,6,0,5]
輸出：返回下面這棵樹(shù)的根節(jié)點(diǎn)：6 / \ 3 5 \ / 2 0 \ 1
提示：
- 給定的數(shù)組的大小在 [1, 1000] 之間形娇。
好久沒(méi)看過(guò)樹(shù)了锰霜，這道題完全沒(méi)有思路，這是討論區(qū)的思路桐早。
遞歸套路三部曲：
- 找終止條件：當(dāng)
l>r時(shí)癣缅，說(shuō)明數(shù)組中已經(jīng)沒(méi)元素了，自然當(dāng)前返回的節(jié)點(diǎn)為null哄酝。 - 每一級(jí)遞歸返回的信息是什么：返回的應(yīng)該是當(dāng)前已經(jīng)構(gòu)造好了最大二叉樹(shù)的
root節(jié)點(diǎn)友存。 - 一次遞歸做了什么：找當(dāng)前范圍為
[l,r]的數(shù)組中的最大值作為root節(jié)點(diǎn)，然后將數(shù)組劃分成[l,bond-1]和[bond+1,r]兩段陶衅，并分別構(gòu)造成root的左右兩棵子最大二叉樹(shù)屡立。
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;
}
};
