654. Maximum Binary Tree

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

Maximum Binary Tree - LeetCode

1. find max & make it as a root

2. split array

3. repeat on splited array (left child / right child)

 

350ms

# 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]) -> TreeNode:
        if not nums:
            return None
        if len(nums) == 1:
            return TreeNode(nums[0])
        
        max_index = 0
        for i, n in enumerate(nums):
            if n > nums[max_index]:
                max_index = i
        
        root = TreeNode(nums[max_index])
        
        root.left = self.constructMaximumBinaryTree(nums[:max_index])
        root.right = self.constructMaximumBinaryTree(nums[max_index+1:])
        
        return root

use iteration instead of recursion

use stack (no duplicate!!!)

180ms

# 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]) -> TreeNode:
        return construct_maximum_binary_tree(nums)


def construct_maximum_binary_tree(nums: List[int]) -> TreeNode:
    stack = []
    for num in nums:
        cur = TreeNode(num)
        while stack and stack[-1].val < cur.val:
            cur.left = stack.pop()
        if stack:
            stack[-1].right = cur 
        stack.append(cur)
    return stack[0]