Manipulate Tree

Create a new tree

654. Maximum Binary Tree (Medium)

TODO: Solve this: https://leetcode.com/problems/maximum-binary-tree/solutions/106156/java-worst-case-o-n-solution/?envType=problem-list-v2&envId=ax22w3wi

Fun Fact

This is also called a Cartesian Tree. One interesting property is that if we do an in-order traversal, we get the array back which we used to create it.

DFS Recursive

Python

def find_max(self, nums, lo, hi) -> int:
    max_element = nums[lo]
    max_index = lo
    for i in range(lo, hi):
        if max_element < nums[i]:
            max_index = i
            max_element = nums[i]
    return max_index


def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
    def recursion(lo: int, hi: int):
        if lo < hi:
            maxi = self.find_max(nums, lo, hi)
            node = TreeNode(val=nums[maxi])
            node.left = recursion(lo, maxi)
            node.right = recursion(maxi + 1, hi)
            return node

    return recursion(0, len(nums))