LeetCode 654: Maximum Binary Tree Solution

Master LeetCode problem 654 (Maximum Binary Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

654. Maximum Binary Tree

Medium

Array Divide and Conquer Stack Tree Monotonic Stack Binary Tree

Problem Explanation

Explanation:

To solve this problem, we can build the maximum binary tree recursively. The idea is to find the maximum value in the input array nums, then create a node with that value as the root. The left subtree will be built recursively on the subarray to the left of the maximum value, and the right subtree will be built on the subarray to the right of the maximum value.

We can define a recursive function that takes the input array and the indices indicating the range of elements to consider for building the subtree. At each step, we find the index of the maximum element in the subarray, create a node with that value, and recursively build the left and right subtrees using the respective subarrays.

The time complexity of this approach is O(n^2) in the worst case, where n is the number of elements in the input array nums. This is because at each step, we may need to search for the maximum element in the subarray, which takes O(n) time. The space complexity is O(n) due to the recursion stack.

Solution Code

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public TreeNode constructMaximumBinaryTree(int[] nums) {
    return construct(nums, 0, nums.length - 1);
}

private TreeNode construct(int[] nums, int start, int end) {
    if (start > end) {
        return null;
    }
    
    int maxIdx = start;
    for (int i = start + 1; i <= end; i++) {
        if (nums[i] > nums[maxIdx]) {
            maxIdx = i;
        }
    }
    
    TreeNode root = new TreeNode(nums[maxIdx]);
    root.left = construct(nums, start, maxIdx - 1);
    root.right = construct(nums, maxIdx + 1, end);
    
    return root;
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 654 (Maximum Binary Tree)?

This page provides optimized solutions for LeetCode problem 654 (Maximum Binary Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 654 (Maximum Binary Tree)?

The time complexity for LeetCode 654 (Maximum Binary Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 654 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 654 in Java, C++, or Python.

Back to LeetCode Solutions