Problem statement

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

Solution

Here we can reuse problem 0654. Maximum Binary Tree.

  1. We need to get arr from our tree, use dfs(node.left) -> node.val -> dfs(node.right) recursion of this.
  2. Add value and use problem 0654.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def construct(self, nums):
        stack = [TreeNode(float('inf'))]
        for num in nums:
            node = TreeNode(num)
            while stack[-1].val < num:
                node.left = stack.pop()
            stack[-1].right = node
            stack.append(node)
        return stack[0].right
    
    def insertIntoMaxTree(self, root, val):
        self.arr = []
        def dfs(node):
            if not node: return
            dfs(node.left)
            self.arr += [node.val]
            dfs(node.right)
            
        dfs(root)
        return self.construct(self.arr + [val])