第一种方法比较直接，利用recursion，时间复杂度Nlog(N);
class Solution {
public:
TreeNode* build_tree(vector<int>& nums, int left, int right){
if(left > right){
return NULL;
}
int max_num = nums[left], max_idx = left;
for(int i=left+1; i<=right; i++){
if(nums[i] > max_num){
max_num = nums[i];
max_idx = i;
}
}
TreeNode *root = new TreeNode(max_num);
root->left = build_tree(nums, left, max_idx-1);
root->right = build_tree(nums, max_idx+1, right);
return root;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
if(nums.empty()){
return NULL;
}
return build_tree(nums, 0, nums.size()-1);
}
};
第二种是O(N), 利用了单调栈的思想，其中用deque来替代普通的stack
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
if(nums.empty()){
return NULL;
}
deque<TreeNode*> st;
for(int i=0; i<nums.size(); i++){
TreeNode *cur = new TreeNode(nums[i]);
while(!st.empty() && st.back()->val < nums[i]){
cur->left = st.back();
st.pop_back();
}
if(!st.empty()){
st.back()->right = cur;
}
st.push_back(cur);
}
return st.front();
}
};
