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 def __init__(self, x):
3 self.val = x
4 self.left = None
5 self.right = None
6
7def mergeTrees(t1, t2):
8 if not t1:
9 return t2
10 if not t2:
11 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 t1This Python solution uses recursion to merge two binary trees. If either node is None, the function returns the other. Otherwise, it sums node values and recursively merges the child nodes.
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.