Sponsored
Sponsored
This 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.
Time Complexity: O(n); Space Complexity: O(h), where n is the total number of nodes and h is the height of the tree.
1class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
10 if (t1 == null) return t2;
11 if (t2 == null) return t1;
12 t1.val += t2.val;
13 t1.left = mergeTrees(t1.left, t2.left);
14 t1.right = mergeTrees(t1.right, t2.right);
15 return t1;
16 }
17}This Java solution uses a recursive method that follows the same logic described above. It either returns the non-null node or merges the values and children recursively.
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.
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.
1#include <iostream>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (!root1) return root2;
if (!root2) return root1;
stack<pair<TreeNode*, TreeNode*>> stk;
stk.push({root1, root2});
while (!stk.empty()) {
auto [n1, n2] = stk.top();
stk.pop();
if (!n1 || !n2) continue;
n1->val += n2->val;
if (!n1->left) {
n1->left = n2->left;
} else {
stk.push({n1->left, n2->left});
}
if (!n1->right) {
n1->right = n2->right;
} else {
stk.push({n1->right, n2->right});
}
}
return root1;
}This C++ solution uses a stack to iteratively merge nodes. We push pairs of nodes to the stack and at each step sum their values and push their left and right children if needed.