654. Maximum Binary Tree

Description:

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.

# 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
'''
[1] divide and conquer)

idea::
1. find max(num) which is pivot
2. recursively call divide and conquer function left-side of pivot
3. recursively call divide and conquer function right-side of pivot
4. set left, right

code::
(below)

-T/C: O(n)+O(logn) # O(n) for finding max, O(nlogn) for dividing nums 
-S/C: O(n)  # when nums are decreasing order
'''
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        
        def dc(nums):
            if len(nums)==0:
                return None
            if len(nums)==1:
                return TreeNode(nums[0])
            
            # setting root
            pivot_num=max(nums)
            pivot_idx=nums.index(pivot_num)
            root=TreeNode(pivot_num)
            
            # setting left node
            left_root=dc(nums[0:pivot_idx])
            
            # setting right node
            right_root=dc(nums[pivot_idx+1:len(nums)])
            
            root.left=left_root
            root.right=right_root
            
            return root
        
        return dc(nums)