Welcome to Subscribe On Youtube
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; } }
-
// 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; } };
-
# 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 root is None or root.val < val: return TreeNode(val, root) root.right = self.insertIntoMaxTree(root.right, val) return root ############ # 998. Maximum Binary Tree II # https://leetcode.com/problems/maximum-binary-tree-ii/ # 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 root and root.val > val: root.right = self.insertIntoMaxTree(root.right, val) return root node = TreeNode(val) node.left = root return node