Leetcode 654 Solution

This article provides solution to leetcode question 654 (maximum-binary-tree)
Categories:
Tags:
Access this page by simply typing in "lcs 654" in your browser address bar if you have bunnylol configured.

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

Solution

# 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, l, r):
        if l > r:
            return None

        opt = (-sys.maxsize -1, 0)
        for i in range(l, r + 1):
            opt = max(opt, (nums[i], i))

        i = opt[1]
        root = TreeNode(nums[i])
        root.left = self._constructMaximumBinaryTree(nums, l, i - 1)
        root.right = self._constructMaximumBinaryTree(nums, i + 1, r)
        return root

    def constructMaximumBinaryTree(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        return self._constructMaximumBinaryTree(nums, 0, len(nums) - 1)