algoadvance

Leetcode 654. Maximum Binary Tree

Problem Statement

Given an integer array nums with no duplicates, you need to construct a maximum binary tree using the following rules:

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

Construct the maximum tree by the given array and output the root node of this tree.

Clarifying Questions

  1. Q: What should be the output? A: The output should be the root of the maximum binary tree.

  2. Q: Can the input nums array be empty? A: No, the problem states that the array has no duplicates, so it should contain at least one element.

  3. Q: Are there any constraints on the number of elements in nums? A: The problem does not specify constraints, but it is typical to assume that nums could be of any reasonable size that can fit in memory.

Strategy

  1. Find the maximum value in the current array segment, which will be the root of the subtree.
  2. Recursively construct the left and right subtrees:
    • The left subtree is constructed from the subarray elements to the left of the maximum element.
    • The right subtree is constructed from the subarray elements to the right of the maximum element.
  3. Combine these steps recursively to build the entire tree.

Code

Here’s a Java implementation for constructing the Maximum Binary Tree:

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return construct(nums, 0, nums.length);
    }
    
    private TreeNode construct(int[] nums, int left, int right) {
        if (left == right) {
            return null;
        }
        
        // Find the index of the maximum value in nums[left:right]
        int maxIndex = left;
        for (int i = left + 1; i < right; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = construct(nums, left, maxIndex);
        root.right = construct(nums, maxIndex + 1, right);
        
        return root;
    }
}

Time Complexity

Let’s analyze the time complexity:

The worst-case scenario occurs when each subdivision leads to maximally unbalanced splits. However, at each recursive step, we still process each element once, leading to an overall complexity of O(n log n) to O(n^2) depending on the structure of splits.

In summary, the average case time complexity is expected to be O(n log n), but the worst case is O(n^2).

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