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.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public 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 C# solution follows the same recursive approach, merging the binary trees by summing overlapping node values and recursively merging 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.
1function
In this JavaScript solution, an iterative approach utilizing a stack is employed. Nodes are iteratively processed and summed, with their children managed in a stack for future processing.