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 <iostream>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode* left;
7 TreeNode* right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
12 if (!root1) return root2;
13 if (!root2) return root1;
14 root1->val += root2->val;
15 root1->left = mergeTrees(root1->left, root2->left);
16 root1->right = mergeTrees(root1->right, root2->right);
17 return root1;
18}This C++ solution uses a similar recursive function. If either node is null, it returns the other. Otherwise, it sums their values and recursively processes their 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.
1using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode MergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null) return t2;
if (t2 == null) return t1;
Stack<TreeNode[]> stack = new Stack<TreeNode[]>();
stack.Push(new TreeNode[] { t1, t2 });
while (stack.Count > 0) {
TreeNode[] t = stack.Pop();
if (t[0] == null || t[1] == null) continue;
t[0].val += t[1].val;
if (t[0].left == null) {
t[0].left = t[1].left;
} else {
stack.Push(new TreeNode[] { t[0].left, t[1].left });
}
if (t[0].right == null) {
t[0].right = t[1].right;
} else {
stack.Push(new TreeNode[] { t[0].right, t[1].right });
}
}
return t1;
}
}This C# solution implements an iterative merging of binary trees using a Stack. As nodes are processed iteratively, their values are summed, and children are managed accordingly.