654. Maximum Binary Tree

LeetCode Problem Link (opens new window)

Given an integer array with no duplicate elements, a maximum binary tree can be built with the following rules:

• The root is the maximum number in the array.
• The left subtree is the maximum tree constructed from the left part to the maximum number.
• The right subtree is the maximum tree constructed from the right part to the maximum number.

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

Example:

Constraints:

The size of the given array is in the range [1, 1000].

Thought Process

The process to construct the maximum binary tree is as follows:

Generally, pre-order traversal is used for tree construction because the middle node is constructed first, followed by recursive construction of the left and right subtrees.

• Define the parameters and return value of the recursive function

The parameter is the array containing elements, and it returns the root node of the binary tree constructed from the array. The return type is a pointer pointing to the node.

The code is as follows:

TreeNode* constructMaximumBinaryTree(vector<int>& nums)

• Define the termination condition

The problem statement assures that the input array size is always greater than or equal to 1, so we don't need to consider cases less than 1. When recursively traversing, if the size of the array passed in is 1, it indicates that we have reached a leaf node.

In this case, a new node should be defined, and the value of this array should be assigned to the new node, then return this node. This indicates that when the size of an array is 1, a new node is constructed and returned.

The code is as follows:

TreeNode* node = new TreeNode(0);
if (nums.size() == 1) {
    node->val = nums[0];
    return node;
}

• Determine the logic of single-layer recursion

There are three steps here:

1. First, find the maximum value in the array and its index. Use the maximum value to construct the root node and use the index to split the array in the next step.

The code is as follows:

int maxValue = 0;
int maxValueIndex = 0;
for (int i = 0; i < nums.size(); i++) {
    if (nums[i] > maxValue) {
        maxValue = nums[i];
        maxValueIndex = i;
    }
}
TreeNode* node = new TreeNode(0);
node->val = maxValue;

2. Construct the left subtree with the left part of the index of the maximum value

Here, maxValueIndex > 0 should be checked to ensure that the left part has at least one value.

The code is as follows:

if (maxValueIndex > 0) {
    vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
    node->left = constructMaximumBinaryTree(newVec);
}

3. Construct the right subtree with the right part of the index of the maximum value

Here, maxValueIndex < (nums.size() - 1) should be checked to ensure that the right part has at least one value.

The code is as follows:

if (maxValueIndex < (nums.size() - 1)) {
    vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());
    node->right = constructMaximumBinaryTree(newVec);
}

With that analysis complete, the full code is as follows:

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* node = new TreeNode(0);
        if (nums.size() == 1) {
            node->val = nums[0];
            return node;
        }
        // Find the maximum value and its index in the array
        int maxValue = 0;
        int maxValueIndex = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > maxValue) {
                maxValue = nums[i];
                maxValueIndex = i;
            }
        }
        node->val = maxValue;
        // Construct the left subtree with the left part of the max value index
        if (maxValueIndex > 0) {
            vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
            node->left = constructMaximumBinaryTree(newVec);
        }
        // Construct the right subtree with the right part of the max value index
        if (maxValueIndex < (nums.size() - 1)) {
            vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());
            node->right = constructMaximumBinaryTree(newVec);
        }
        return node;
    }
};

The code above is relatively verbose and inefficient, as each slice operation requires a new vector (array), but the logic is clear.

The optimization approach is similar to that in 0106.Construct Binary Tree from Inorder and Postorder Traversal (opens new window), where instead of defining a new array each time, you operate directly on the original array using index references.

The optimized code is as follows:

class Solution {
private:
    // Construct a binary tree in the left-closed, right-open interval [left, right)
    TreeNode* traversal(vector<int>& nums, int left, int right) {
        if (left >= right) return nullptr;

        // Split point index: maxValueIndex
        int maxValueIndex = left;
        for (int i = left + 1; i < right; ++i) {
            if (nums[i] > nums[maxValueIndex]) maxValueIndex = i;
        }

        TreeNode* root = new TreeNode(nums[maxValueIndex]);

        // Left closed, right open interval: [left, maxValueIndex)
        root->left = traversal(nums, left, maxValueIndex);

        // Left closed, right open interval: [maxValueIndex + 1, right)
        root->right = traversal(nums, maxValueIndex + 1, right);

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

Extension

You may notice that the code above looks cleaner. This is primarily because the second version allows null nodes to enter recursion, so there is no need to add conditional checks to prevent null nodes from entering recursion.

The first version of recursion (with conditional checks to prevent null nodes from entering recursion):

if (maxValueIndex > 0) { // This check is to prevent null nodes from entering recursion
    vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
    node->left = constructMaximumBinaryTree(newVec);
}

if (maxValueIndex < (nums.size() - 1)) { // This check is to prevent null nodes from entering recursion
    vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());
    node->right = constructMaximumBinaryTree(newVec);
}

The second version of recursion: (with no conditional check)

root->left = traversal(nums, left, maxValueIndex);

root->right = traversal(nums, maxValueIndex + 1, right);

The second version allows null nodes to enter recursion, so there is no conditional check. Of course, the termination condition needs to be changed accordingly.

In the first version, recursion terminates when a leaf node is encountered, as null nodes do not enter recursion.

In the second version, the corresponding termination condition is when a null node (or an empty array segment) is encountered, indicating the end of recursion.

Summary

This problem is similar to 0106.Construct Binary Tree from Inorder and Postorder Traversal (opens new window), but simpler.

It's important to try to avoid defining new arrays for each split in similar problems, where an array is used to construct a binary tree. Instead, work directly on the original array using index references to save both time and space overhead.

Some might also wonder when to add an if at the front of a recursive function and when not to. I have provided some explanation at the end.

It basically boils down to different implementation styles: In general, if null nodes (null pointers) are allowed to enter recursion, skip the if. Otherwise, add an if to restrict it. The termination condition would also adjust accordingly.

Solutions in Other Languages

Java

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructMaximumBinaryTree1(nums, 0, nums.length);
    }

    public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) {
        if (rightIndex - leftIndex < 1) {// No elements
            return null;
        }
        if (rightIndex - leftIndex == 1) {// Only one element
            return new TreeNode(nums[leftIndex]);
        }
        int maxIndex = leftIndex;// Location of the maximum value
        int maxVal = nums[maxIndex];// Maximum value
        for (int i = leftIndex + 1; i < rightIndex; i++) {
            if (nums[i] > maxVal){
                maxVal = nums[i];
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(maxVal);
        // Divide left and right subtrees based on maxIndex
        root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);
        root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);
        return root;
    }
}

Python

(Version 1) Basic version

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        if len(nums) == 1:
            return TreeNode(nums[0])
        node = TreeNode(0)
        # Find the maximum value and its index in the array
        maxValue = 0
        maxValueIndex = 0
        for i in range(len(nums)):
            if nums[i] > maxValue:
                maxValue = nums[i]
                maxValueIndex = i
        node.val = maxValue
        # Construct the left subtree with the left part of the max value index
        if maxValueIndex > 0:
            new_list = nums[:maxValueIndex]
            node.left = self.constructMaximumBinaryTree(new_list)
        # Construct the right subtree with the right part of the max value index
        if maxValueIndex < len(nums) - 1:
            new_list = nums[maxValueIndex+1:]
            node.right = self.constructMaximumBinaryTree(new_list)
        return node
        

(Version 2) Using indices

class Solution:
    def traversal(self, nums: List[int], left: int, right: int) -> TreeNode:
        if left >= right:
            return None
        maxValueIndex = left
        for i in range(left + 1, right):
            if nums[i] > nums[maxValueIndex]:
                maxValueIndex = i
        root = TreeNode(nums[maxValueIndex])
        root.left = self.traversal(nums, left, maxValueIndex)
        root.right = self.traversal(nums, maxValueIndex + 1, right)
        return root

    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        return self.traversal(nums, 0, len(nums))

(Version 3) Using slicing

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        if not nums:
            return None
        max_val = max(nums)
        max_index = nums.index(max_val)
        node = TreeNode(max_val)
        node.left = self.constructMaximumBinaryTree(nums[:max_index])
        node.right = self.constructMaximumBinaryTree(nums[max_index+1:])
        return node
        

Go

func constructMaximumBinaryTree(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil 
    }
    // Find the maximum value
    index := findMax(nums)
    // Construct the binary tree
    root := &TreeNode {
        Val: nums[index],
        Left: constructMaximumBinaryTree(nums[:index]),   // Left side
        Right: constructMaximumBinaryTree(nums[index+1:]),// Right side
        }
    return root
}
func findMax(nums []int) (index int) {
    for i, v := range nums {
        if nums[index] < v {
            index = i
        }
    }
    return 
}

JavaScript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var constructMaximumBinaryTree = function (nums) {
    const BuildTree = (arr, left, right) => {
        if (left > right)
            return null;
        let maxValue = -1;
        let maxIndex = -1;
        for (let i = left; i <= right; ++i) {
            if (arr[i] > maxValue) {
                maxValue = arr[i];
                maxIndex = i;
            }
        }
        let root = new TreeNode(maxValue);
        root.left = BuildTree(arr, left, maxIndex - 1);
        root.right = BuildTree(arr, maxIndex + 1, right);
        return root;
    }
    let root = BuildTree(nums, 0, nums.length - 1);
    return root;
};

TypeScript

New array method:

function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
    if (nums.length === 0) return null;
    let maxIndex: number = 0;
    let maxVal: number = nums[0];
    for (let i = 1, length = nums.length; i < length; i++) {
        if (nums[i] > maxVal) {
            maxIndex = i;
            maxVal = nums[i];
        }
    }
    const rootNode: TreeNode = new TreeNode(maxVal);
    rootNode.left = constructMaximumBinaryTree(nums.slice(0, maxIndex));
    rootNode.right = constructMaximumBinaryTree(nums.slice(maxIndex + 1));
    return rootNode;
};

Using array indices:

function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
    // Closed interval [begin, end)
    function recur(nums: number[], begin: number, end: number): TreeNode | null {
        if (begin === end) return null;
        let maxIndex: number = begin;
        let maxVal: number = nums[begin];
        for (let i = begin + 1; i < end; i++) {
            if (nums[i] > maxVal) {
                maxVal = nums[i];
                maxIndex = i;
            }
        }
        const rootNode: TreeNode = new TreeNode(maxVal);
        rootNode.left = recur(nums, begin, maxIndex);
        rootNode.right = recur(nums, maxIndex + 1, end);
        return rootNode;
    }
    return recur(nums, 0, nums.length);
};

C

struct TreeNode* traversal(int* nums, int left, int right) {
    if(left >= right)
        return NULL;
    
    int maxIndex = left;
    int i;
    for(i = left + 1; i < right; i++) {
        if(nums[i] > nums[maxIndex])
            maxIndex = i;
    }
    
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = nums[maxIndex];
    node->left = traversal(nums, left, maxIndex);
    node->right = traversal(nums, maxIndex + 1, right);
    return node;
}

struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize){
    return traversal(nums, 0, numsSize);
}

Swift

func constructMaximumBinaryTree(_ nums: inout [Int]) -> TreeNode? {
    return traversal(&nums, 0, nums.count)
}

func traversal(_ nums: inout [Int], _ left: Int, _ right: Int) -> TreeNode? {
    if left >= right {
        return nil
    }
    
    var maxValueIndex = left
    for i in (left + 1)..<right {
        if nums[i] > nums[maxValueIndex] {
            maxValueIndex = i
        }
    }
    
    let root = TreeNode(nums[maxValueIndex])
    
    root.left = traversal(&nums, left, maxValueIndex)
    root.right = traversal(&nums, maxValueIndex + 1, right)
    return root
}

Scala

object Solution {
  def constructMaximumBinaryTree(nums: Array[Int]): TreeNode = {
    if (nums.size == 0) return null
    var maxIndex = 0
    var maxValue = Int.MinValue
    for (i <- nums.indices) {
      if (nums(i) > maxValue) {
        maxIndex = i
        maxValue = nums(i)
      }
    }

    var root = new TreeNode(maxValue, null, null)

    root.left = constructMaximumBinaryTree(nums.slice(0, maxIndex))
    root.right = constructMaximumBinaryTree(nums.slice(maxIndex + 1, nums.length))

    root 
  }
}

Rust

New Array:

use std::cell::RefCell;
use std::rc::Rc;
impl Solution{
    pub fn construct_maximum_binary_tree(mut nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        if nums.is_empty() {
            return None;
        }
        let mut max_value_index = 0;
        for i in 0..nums.len() {
            if nums[max_value_index] < nums[i] {
                max_value_index = i;
            }
        }
        let right = Self::construct_maximum_binary_tree(nums.split_off(max_value_index + 1));
        let root = nums.pop().unwrap();
        let left = Self::construct_maximum_binary_tree(nums);
        Some(Rc::new(RefCell::new(TreeNode {
            val: root,
            left,
            right,
        })))
    }
}

Array indices:

use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn construct_maximum_binary_tree(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        Self::traversal(&nums, 0, nums.len())
    }

    pub fn traversal(nums: &Vec<i32>, left: usize, right: usize) -> Option<Rc<RefCell<TreeNode>>> {
        if left >= right {
            return None;
        }
        let mut max_value_index = left;
        for i in left + 1..right {
            if nums[max_value_index] < nums[i] {
                max_value_index = i;
            }
        }
        let mut root = TreeNode::new(nums[max_value_index]);
        root.left = Self::traversal(nums, left, max_value_index);
        root.right = Self::traversal(nums, max_value_index + 1, right);
        Some(Rc::new(RefCell::new(root)))
    }
}

C#

public TreeNode ConstructMaximumBinaryTree(int[] nums)
{
    if (nums.Length == 0) return null;
    int rootValue = nums.Max();
    TreeNode root = new TreeNode(rootValue);
    int rootIndex = Array.IndexOf(nums, rootValue);

    root.left = ConstructMaximumBinaryTree(nums.Take(rootIndex).ToArray());
    root.right = ConstructMaximumBinaryTree(nums.Skip(rootIndex + 1).ToArray());
    return root;

}