Datastructure and Algorithm: DAY 91. Leetcode: 288/2752
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, 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:
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]
1 2
Example 2: {% asset_img e2.jpg e2%}
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]
1 2
Example 3: {% asset_img e3.jpg e3%}
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]
1 2
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
## Solution Because the new val is added at the end of the array, we can compare with the root node, - If it is larger than the root, then val is the new root and the original root is its left subtree (since val is to the right of the original root's value in the array). - If it is smaller than the root node, it means that val must be recursively added to the right node of the original root. Note that recursion may change the root of the right subtree, so reassign the right node of the root node. Finally, if the recursive root is empty, a new leaf node can be returned directly.
```python # 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 insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]: if not root: return TreeNode(val) if val > root.val: cur = TreeNode(val) cur.left = root return cur root.right = self.insertIntoMaxTree(root.right, val) return root
