You are given two binary trees root1 and root2.
Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.
Return the merged tree.
Note: The merging process must start from the root nodes of both trees.
Example 1:
Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7] Output: [3,4,5,5,4,null,7]
Example 2:
Input: root1 = [1], root2 = [1,2] Output: [2,2]
Constraints:
[0, 2000].-104 <= Node.val <= 104This approach utilizes recursion to traverse both trees simultaneously. If both node values are non-null, we sum them up as the new value and recursively merge their left and right children. If one node is null, we return the non-null node.
This C solution uses a recursive function mergeTrees. We check if either of the current nodes is null and return the other node. If neither is null, we sum their values, then recursively merge their left and right children.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n); Space Complexity: O(h), where n is the total number of nodes and h is the height of the tree.
This approach uses an iterative method with a stack to simulate the recursive calls for merging the two binary trees. We traverse the trees using a stack and merge nodes at each level iteratively.
This C solution uses a stack to perform an iterative merge of the binary trees. We manage pairs of nodes to process, summing their values and pushing their children onto the stack for subsequent processing.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n); Space Complexity: O(h), where n is the total number of nodes and h is the maximum height of the two trees.
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(n); Space Complexity: O(h), where n is the total number of nodes and h is the height of the tree. |
| Iterative Approach | Time Complexity: O(n); Space Complexity: O(h), where n is the total number of nodes and h is the maximum height of the two trees. |
Merge Two Binary Trees - Leetcode 617 • NeetCode • 61,579 views views
Watch 9 more video solutions →Practice Merge Two Binary Trees with our built-in code editor and test cases.
Practice on FleetCode