LeetCode 654. Maximum Binary Tree

Questions: https://leetcode.com/problems/maximum-binary-tree/

As it is explained in a previous tree question. A recursive solution to tree problems is much easier to come by. In this case, we just need to find the maximum in the array, and apply the definition of the maximum binary tree as it's described in the question.

A general approach that I took to solve this type of question is to write down the solution to the general case with the minimum size. For example, we will start with len(nums) = 2. In this case, we will have max_pos either in position 0 or 1. Then either our leftTree or rightTree will be empty. Given this thought, you know your base case has to have the case when nums are passed in as an empty list [] with size 0, and there you go, in under 5 minutes, you already solved the problem labeled as medium difficulty. I doubt this question is actually of medium difficulty. I will challenge myself to an alternative way of solving this problem in another time.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def constructMaximumBinaryTree(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        n = len(nums)
        if n == 0:
            return None

        max_pos = 0
        curmax = nums[max_pos]
        for i in range(n):
            if curmax < nums[i]:
                curmax = nums[i]
                max_pos = i
        root = TreeNode(nums[max_pos])
        leftTree = self.constructMaximumBinaryTree(nums[:max_pos])
        rightTree = self.constructMaximumBinaryTree(nums[max_pos+1:])
        root.left = leftTree
        root.right = rightTree
        return root