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.
1function TreeNode(val) {
2 this.val = val;
3 this.left = this.right = null;
4}
5
6var mergeTrees = function(t1, t2) {
7 if (!t1) return t2;
8 if (!t2) return t1;
9 t1.val += t2.val;
10 t1.left = mergeTrees(t1.left, t2.left);
11 t1.right = mergeTrees(t1.right, t2.right);
12 return t1;
13};This JavaScript solution uses recursion to merge two binary trees. If either node is undefined, the function returns the other. Otherwise, it sums node values and recursively processes 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.
1class
This Python solution uses a stack for an iterative merge. By pairing nodes, we handle the overlap and non-overlap cases explicitly by managing a stack to traverse and combine nodes iteratively.