Formatted question description: https://leetcode.ca/all/998.html
998. Maximum Binary Tree II (Medium)
We are given the root
node of a maximum tree: a tree where every node has a value greater than any other value in its subtree.
Just as in the previous problem, the given tree was constructed from an list A
(root = Construct(A)
) recursively with the following Construct(A)
routine:
- If
A
is empty, returnnull
. - Otherwise, let
A[i]
be the largest element ofA
. Create aroot
node with valueA[i]
. - The left child of
root
will beConstruct([A[0], A[1], ..., A[i-1]])
- The right child of
root
will beConstruct([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]
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]
Note:
1 <= B.length <= 100
Companies:
Facebook
Related Topics:
Tree
Similar Questions:
Solution 1.
- Find insertion point: Keep repeating the following logic until
node
becomesNULL
- If
val < node->val
, go right. - Otherwise, break.
- If
- Assume
prev
is the parent ofnode
. The new node should be the right child ofprev
andnode
(which might beNULL
) should be the left child of the new node.
// OJ: https://leetcode.com/problems/maximum-binary-tree-ii/
// Time: O(N)
// Space: O(1)
class Solution {
public:
TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
TreeNode *node = root, *prev = NULL;
while (node && val < node->val) {
prev = node;
node = node->right;
}
auto n = new TreeNode(val);
if (prev) prev->right = n;
else root = n;
n->left = node;
return root;
}
};
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode insertIntoMaxTree(TreeNode root, int val) {
TreeNode newNode = new TreeNode(val);
if (root == null)
return newNode;
if (val > root.val) {
newNode.left = root;
return newNode;
}
TreeNode temp = root;
while (temp.val > val) {
TreeNode rightChild = temp.right;
if (rightChild == null) {
temp.right = newNode;
break;
} else if (rightChild.val < val) {
temp.right = newNode;
newNode.left = rightChild;
break;
} else
temp = temp.right;
}
return root;
}
}