algoadvance

Leetcode 654. Maximum Binary Tree

Problem Statement

Given an integer array nums, construct the maximum binary tree. The maximum binary tree is defined as follows:

  1. The root is the maximum number in nums.
  2. The left subtree is the maximum tree constructed from the left part subarray divided by the maximum number.
  3. The right subtree is the maximum tree constructed from the right part subarray divided by the maximum number.

Return the root node of the maximum binary tree.

Clarifying Questions

  1. Input Constraints:
    • Can the input array contain duplicates?
    • What is the range of the values in the input array?
    • What is the maximum length of the input array?
  2. Output Requirements:
    • Should the tree be returned in any specific format, or should it simply be the root node of the binary tree?

Code

#include <vector>
#include <algorithm>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return construct(nums, 0, nums.size());
    }

private:
    TreeNode* construct(const vector<int>& nums, int left, int right) {
        if (left == right) return nullptr;
        
        // Find the index of the maximum value in the current range
        int maxIndex = left;
        for (int i = left + 1; i < right; ++i) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        
        // Create the root node with the maximum value
        TreeNode* node = new TreeNode(nums[maxIndex]);
        
        // Recursively construct the left and right subtrees
        node->left = construct(nums, left, maxIndex);
        node->right = construct(nums, maxIndex + 1, right);
        
        return node;
    }
};

Strategy

  1. Identify the Base Case:
    • If left index equals right index, return nullptr.
  2. Recursive Step:
    • Find the maximum element in the range [left, right) which will be the root for the current subtree.
    • Create a TreeNode with the maximum value.
    • Construct the left subtree with the elements to the left of the maximum value.
    • Construct the right subtree with the elements to the right of the maximum value.
  3. Procedure:
    • Use a helper function construct that takes the range [left, right) as parameters.
    • Recursively divide the array and build the tree based on the found maximum elements in each section.

Time Complexity

The time complexity for this approach is O(n^2) in the worst-case scenario:

In the average case, the complexity tends to be better but is still bounded by O(n^2) due to unbalanced split possibilities.

For optimizing, a segment tree or a monotonic stack could potentially reduce the overhead to O(n) but increases implementation complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI