#998
Maximum Binary Tree II
specialist · 625 · lc medium +29 · verified · 70.3% accepted · 565 likes · top 79%
Description
A maximum tree is a tree in which every node's value exceeds all values in its subtree.
You are given the root of a maximum binary tree constructed from a list a using the following Construct(a) routine:
- If a is empty, return null.
- Let a[i] be the largest element of a. Create a root node with value a[i].
- The left child is Construct([a[0], ..., a[i-1]]).
- The right child is Construct([a[i+1], ..., a[a.length-1]]).
- Return root.
You are also given an integer val. Let b be a with val appended; all values in b are unique.
Return Construct(b).
Example 1:
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:
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:
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]
Code
1
2
3
4
5
6
7
8
9