C++ Solution with recursion


  • 0
    Y

    If maximum is the first element in vector, construct only right vector. If maximum is the last element in vector, construct only left vector.

    class Solution {
    public:
        int findMax(vector<int>& a) {
            int amax=INT_MIN;
            for (int n : a) {
                amax = max(amax, n);
            }
            return amax;
        }
        
        TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
            
            int currMax = findMax(nums);
            TreeNode* root = new TreeNode(currMax);
            TreeNode* left=NULL;
            TreeNode* right=NULL;
            for (int i=0; i<nums.size(); i++) {
                if (nums[i] == currMax) {
                    if (i != 0 ) {
                        vector<int> leftarr(nums.begin(), nums.begin()+i);
                        left = constructMaximumBinaryTree(leftarr);
                    }
                    if (i != nums.size()-1) {
                        vector<int> rightarr(nums.begin()+i+1, nums.end());
                        right = constructMaximumBinaryTree(rightarr);
                    }
                }
            }
            if (left) {
                root->left = left;
            }
            if (right) {
                root->right = right;
            }
            return root;
        }
    };
    

Log in to reply
 

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