Maximum Binary Tree Python Solution with Tests

lcpy gen -n 654   # by problem number
lcpy gen -s maximum_binary_tree   # by problem name

Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]
Explanation: The recursive calls are as follow:
- The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5].
    - The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1].
        - Empty array, so no child.
        - The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1].
            - Empty array, so no child.
            - Only one element, so child is a node with value 1.
    - The largest value in [0,5] is 5. Left prefix is [0] and right suffix is [].
        - Only one element, so child is a node with value 0.
        - Empty array, so no child.

Input: nums = [3,2,1]
Output: [3,null,2,null,1]

from leetcode_py import TreeNode


class Solution:
    # Time: O(n) - each index is pushed and popped at most once
    # Space: O(n) - stack holds the right spine of the tree
    def construct_maximum_binary_tree(self, nums: list[int]) -> TreeNode[int] | None:
        stack: list[TreeNode[int]] = []
        for num in nums:
            node = TreeNode(num)
            while stack and stack[-1].val < num:
                node.left = stack.pop()
            if stack:
                stack[-1].right = node
            stack.append(node)
        return stack[0] if stack else None