Leetcode 998: Maximum Binary Tree II
You are given the root of a maximum binary tree and an integer val. The task is to insert val into the tree by constructing a new maximum binary tree with a list that contains val appended to the original list used to construct the tree.
Problem
Approach
Steps
Complexity
Input: The input consists of a binary tree root, which is constructed from a list a, and an integer val to be appended to this list to form a new binary tree.
Example: root = [10, 4, 7, null, null, 5], val = 12
Constraints:
• 1 <= Node.val <= 100
• 1 <= val <= 100
• The number of nodes in the tree is between 1 and 100.
Output: Return the root of the newly constructed maximum binary tree after appending val to the original tree's list.
Example: Output: [12, 10, null, 4, 7, null, null, 5]
Constraints:
• The tree must maintain the maximum binary tree property after insertion.
Goal: The goal is to create a new maximum binary tree by appending val to the original list and constructing a new tree following the properties of a maximum binary tree.
Steps:
• Step 1: Append the new value val to the original list a.
• Step 2: Reconstruct the maximum binary tree using the updated list b.
• Step 3: Return the root of the newly constructed tree.
Goal: The constraints ensure the tree has unique values and that the range for both node values and val are between 1 and 100.
Steps:
• The number of nodes is between 1 and 100.
• All node values are unique.
Assumptions:
• The tree is always constructed from a unique set of values.
• Input: root = [10, 4, 7, null, null, 5], val = 12
• Explanation: In this example, after appending 12 to the list [4, 10, 7, 5], the new tree has 12 as the root.
• Input: root = [15, 8, 12, null, 10], val = 14
• Explanation: In this case, after appending 14 to the list [8, 15, 12, 10], the new tree has 14 as the root.
Approach: The approach involves modifying the original list by appending val and then reconstructing the binary tree following the maximum binary tree rules.
Observations:
• We need to reconstruct the tree with a new root after appending val to the list.
• This approach is similar to the original tree construction, except we need to append the new value first.
Steps:
• Step 1: Append val to the original list.
• Step 2: Use the Construct routine to rebuild the tree from the updated list.
• Step 3: Return the newly constructed tree's root.
Empty Inputs:
• The tree is never empty as per the constraints.
Large Inputs:
• Ensure that the solution works for trees with up to 100 nodes.
Special Values:
• If the value val is larger than any existing node values, it should become the root.
Constraints:
• All values in the tree are unique, so no duplicates will exist.
TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
if(root != NULL && root->val > val) {
root->right = insertIntoMaxTree(root->right, val);
return root;
}
TreeNode* node = new TreeNode(val);
node->left = root;
return node;
}
1 : Function Definition
TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
Defines the function `insertIntoMaxTree`, which takes a root node of a binary tree and a value `val` to insert in the tree following max-heap properties.
2 : Condition Check
if(root != NULL && root->val > val) {
Checks if the root is not null and its value is greater than the value to be inserted. This ensures that the value is placed in the right subtree if it’s smaller than the current root.
3 : Recursive Call
root->right = insertIntoMaxTree(root->right, val);
Recursively calls the function on the right child of the root to insert the value into the correct position.
4 : Return Root
return root;
Returns the root node after the insertion, maintaining the structure of the max tree.
5 : Node Creation
TreeNode* node = new TreeNode(val);
Creates a new node with the given value `val`.
6 : Assign Left Child
node->left = root;
Sets the newly created node’s left child to be the current root. This node becomes the new root of the tree.
7 : Return New Root
return node;
Returns the newly created node as the new root of the tree.
Best Case: O(n) - Constructing the tree from the list of n elements.
Average Case: O(n) - Similar to the best case as we rebuild the tree from the updated list.
Worst Case: O(n) - Even for the worst case, the complexity remains linear as we rebuild the tree.
Description: Time complexity is O(n), where n is the number of nodes in the tree.
Best Case: O(n) - Even in the best case, space complexity remains linear.
Worst Case: O(n) - The space complexity is proportional to the size of the tree.
Description: The space complexity is linear in terms of the number of nodes in the tree.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus