# 0998. Maximum Binary Tree II

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

## Description

A **maximum tree** is a tree where every node has a value greater than any other value in its subtree.

You are given the `root` of a maximum binary tree and an integer `val`.

Just as in the [previous problem](https://leetcode.com/problems/maximum-binary-tree/), the given tree was constructed from a list `a` (`root = Construct(a)`) recursively with the following `Construct(a)` routine:

* If `a` is empty, return `null`.
* Otherwise, let `a[i]` be the largest element of `a`. Create a `root` node with the value `a[i]`.
* The left child of `root` will be `Construct([a[0], a[1], ..., a[i - 1]])`.
* The right child of `root` will be `Construct([a[i + 1], a[i + 2], ..., a[a.length - 1]])`.
* Return `root`.

Note that we were not given `a` directly, only a root node `root = Construct(a)`.

Suppose `b` is a copy of `a` with the value `val` appended to it. It is guaranteed that `b` has unique values.

Return `Construct(b)`.

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/08/09/maxtree1.JPG)

```
**Input:** root = [4,1,3,null,null,2], val = 5
**Output:** [5,4,null,1,3,null,null,2]
**Explanation:** a = [1,4,2,3], b = [1,4,2,3,5]
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/08/09/maxtree21.JPG)

```
**Input:** root = [5,2,4,null,1], val = 3
**Output:** [5,2,4,null,1,null,3]
**Explanation:** a = [2,1,5,4], b = [2,1,5,4,3]
```

**Example 3:**

![](https://assets.leetcode.com/uploads/2021/08/09/maxtree3.JPG)

```
**Input:** root = [5,2,3,null,1], val = 4
**Output:** [5,2,4,null,1,3]
**Explanation:** a = [2,1,5,3], b = [2,1,5,3,4]
```

**Constraints:**

* The number of nodes in the tree is in the range `[1, 100]`.
* `1 <= Node.val <= 100`
* All the values of the tree are **unique**.
* `1 <= val <= 100`

## ac

```java
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/solutions/0998-maximum-binary-tree-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.