Maximum Binary Tree (Leetcode 654)

第一种方法比较直接，利用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();
    }
};