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.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2) {
11 if (!root1) return root2;
12 if (!root2) return root1;
13 root1->val += root2->val;
14 root1->left = mergeTrees(root1->left, root2->left);
15 root1->right = mergeTrees(root1->right, root2->right);
16 return root1;
17}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.
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>
2#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.