Leetcode 617: Merge Two Binary Trees
Solution to LeetCode 617: Merge Two Binary Trees Problem
Given two binary trees, merge them into a new binary tree where overlapping nodes are summed, and non-overlapping nodes are retained as they are.
Problem
Approach
Steps
Complexity
Input: The input consists of two binary trees, represented by their root nodes. Each node contains an integer value.
Example: root1 = [1, 3, 2, 5], root2 = [2, 1, 3, None, 4, None, 7]
Constraints:
• The number of nodes in each tree is in the range [0, 2000].
• -10^4 <= Node.val <= 10^4
Output: Return the root of the merged binary tree.
Example: [3, 4, 5, 5, 4, None, 7]
Constraints:
• The merged tree should be returned as the root node of the new binary tree.
Goal: Merge two binary trees by summing overlapping nodes and using non-overlapping nodes directly.
Steps:
• 1. If both nodes are non-null, sum the values and recursively merge the left and right subtrees.
• 2. If one of the nodes is null, return the non-null node as it is.
• 3. If both nodes are null, return null.
Goal: Both trees are binary trees, and their number of nodes and values are within the given constraints.
Steps:
• The number of nodes in both trees is between 0 and 2000.
• Node values are between -10^4 and 10^4.
Assumptions:
• Both input trees are valid binary trees.
• Input: root1 = [1, 3, 2, 5], root2 = [2, 1, 3, None, 4, None, 7]
• Explanation: In this example, the root nodes (1 and 2) are merged into 3. The left children (3 and 1) are merged into 4, and similarly for the right children. The leaves are merged by summing the node values.
Approach: We will merge the trees recursively by comparing the values of the nodes and summing them where both nodes are non-null, or directly using the non-null node if one is null.
Observations:
• The problem is a classic example of recursion where we merge two binary trees.
• We will recursively traverse both trees and merge them by summing the overlapping nodes and retaining the non-overlapping nodes.
Steps:
• 1. Create a new TreeNode to hold the merged tree.
• 2. If both nodes are non-null, sum their values and recursively merge their left and right subtrees.
• 3. If one of the nodes is null, use the other node as the result for that subtree.
Empty Inputs:
• If both trees are empty, return null.
Large Inputs:
• Handle cases where the trees have up to 2000 nodes.
Special Values:
• Trees with null nodes or trees that have only one node.
Constraints:
• Ensure that the function handles the merging of trees efficiently within the input size constraints.
TreeNode* mergeTrees(TreeNode* r1, TreeNode* r2) {
TreeNode* ans = new TreeNode(0);
if(r1 == NULL && r2 == NULL) return NULL;
if(r1 != NULL && r2 != NULL)
ans->val = r1->val + r2->val;
else if(r1 == NULL)
ans->val = r2->val;
else
ans->val = r1->val;
ans->left = mergeTrees(r1?r1->left:NULL, r2?r2->left:NULL);
ans->right = mergeTrees(r1?r1->right:NULL, r2?r2->right:NULL);
return ans;
}
1 : Function Declaration
TreeNode* mergeTrees(TreeNode* r1, TreeNode* r2) {
Defines the `mergeTrees` function that takes two binary tree nodes (`r1` and `r2`) as input and returns a new merged tree rooted at `ans`.
2 : Node Creation
TreeNode* ans = new TreeNode(0);
Creates a new `TreeNode` named `ans` and initializes its value to `0`. This will hold the merged values from both trees.
3 : Base Case (NULL check)
if(r1 == NULL && r2 == NULL) return NULL;
Checks if both input nodes are NULL. If so, it returns NULL because there is no tree to merge.
4 : Both Nodes Present
if(r1 != NULL && r2 != NULL)
Checks if both input nodes (`r1` and `r2`) are non-NULL. If true, their values will be added together to form the value of the merged node.
5 : Sum Values of Both Nodes
ans->val = r1->val + r2->val;
If both nodes are non-NULL, the values from both nodes (`r1->val` and `r2->val`) are summed and stored in `ans->val`.
6 : Only First Node Present
else if(r1 == NULL)
Checks if the first node (`r1`) is NULL, meaning only `r2` has a node at this position in the tree.
7 : Use Value from Second Node
ans->val = r2->val;
If `r1` is NULL, the value from `r2` is assigned to `ans->val`, as `r2` is the only valid node.
8 : Only Second Node Present
else
If neither of the previous conditions was met, it implies that `r2` is NULL and only `r1` is valid at this position.
9 : Use Value from First Node
ans->val = r1->val;
If `r2` is NULL, the value from `r1` is assigned to `ans->val`, as `r1` is the only valid node.
10 : Recursive Left Subtree Merge
ans->left = mergeTrees(r1?r1->left:NULL, r2?r2->left:NULL);
Recursively merges the left subtrees of `r1` and `r2`. If a tree is missing a left child, it passes NULL instead.
11 : Recursive Right Subtree Merge
ans->right = mergeTrees(r1?r1->right:NULL, r2?r2->right:NULL);
Recursively merges the right subtrees of `r1` and `r2`. Similar to the left subtree, NULL is passed if a tree has no right child.
12 : Return Merged Tree
return ans;
Returns the root of the merged tree, which has been constructed by recursively merging nodes and their children.
Best Case: O(N)
Average Case: O(N)
Worst Case: O(N)
Description: The time complexity is O(N) where N is the total number of nodes in both trees, as we visit each node once.
Best Case: O(H)
Worst Case: O(H)
Description: The space complexity is O(H) where H is the height of the tree due to the recursive call stack.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus