Two C++ solution with explanation O(n)time O(1)space no recursion And O(n^2) recursion


  • 1
    W

    Solution 1:
    The idea is we traverse from left to right. So if the current node->val more than the head->val we just put the head to the current node's left, because the current node aways at the right of the head. And then make the current node be the new head. we the current node->val is less than head, keep travel the right of head, right->right, right->right->right ......, when find a right node->val less than the current node->val, we put the current node to the right node's place and put the right node to the current node's left. But if all right node are all more than the current node, we need put the current node to the last right node 's right.

     //O(n) method
        TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
            if(nums.size()==0)
                return nullptr;
            TreeNode *head=new TreeNode(nums[0]);
            TreeNode *rightNode=head;
            for(int i=1;i<nums.size();++i)
            {
                TreeNode *nowNode=new TreeNode(nums[i]);
                rightNode=head;
                if(head->val<nowNode->val)
                {
                    nowNode->left=head;
                    head=nowNode;
                }else
                {
                    bool find=false;
                    while(rightNode->right)
                    {
                        if(nowNode->val>rightNode->right->val)
                        {
                            nowNode->left=rightNode->right;
                            rightNode->right=nowNode;
                            find=true;
                            break;
                        }else
                            rightNode=rightNode->right;
                    }
                    if(find==false)
                        rightNode->right=nowNode;
                }                           
            }
            return head;
        }
    

    Solution 2:
    Easy to understand. just find the max num as the head, and do same to the left part and right part.

    //O(n^2) method
        TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
            if(nums.size()==0)
                return nullptr;
            return helpBuildTree(nums,0,nums.size()-1);
        }
        TreeNode* helpBuildTree(vector<int>& nums,int left,int right) {
            if(left>right)
                return nullptr;
            int maxIndex=left,maxNum=nums[left];
            for(int i=left+1;i<=right;++i)
            {
                if(nums[i]>maxNum)
                {
                    maxNum=nums[i];
                    maxIndex=i;
                }
            }
            //cout<<maxNum<<" ";
            TreeNode *head=new TreeNode(maxNum);
            head->left=helpBuildTree(nums,left,maxIndex-1);
            head->right=helpBuildTree(nums,maxIndex+1,right);
            return head;
            
        }
    

  • 0
    S

    @wzk623 nice solution ! Thanks!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.