permalink: /archive/posts/daily_leetcode_4/
date: Mon Sep 26 2022 00:00:00 GMT+0000 (Coordinated Universal Time)

654. Maximum Binary Tree

Medium

You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:

1. Create a root node whose value is the maximum value in nums.
2. Recursively build the left subtree on the subarray prefix to the left of the maximum value.
3. Recursively build the right subtree on the subarray suffix to the right of the maximum value.

Return the maximum binary tree built from nums.

Well I already fucked up the one-per-day thing, but it was the weekend to be fair. I don't like even looking at code after 40+ hours of doing so during the week. But anyway, it's Monday again, so here's the next one.

This one's pretty easy to comprehend, we just iterate through nums and split the array by one for each child node we create, until the array is empty.

# 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]) -> Optional[TreeNode]:
        if nums:
            k, v = max(enumerate(nums), key=lambda x: x[1])
            curr_node = TreeNode(v)
            
            curr_node.left = self.constructMaximumBinaryTree(nums[:k])
            curr_node.right = self.constructMaximumBinaryTree(nums[k + 1:])
            
            return curr_node