617. Merge Two Binary Trees
Last updated
Last updated
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}/**
* Time complexity : O(m). A total of m nodes need to be traversed.
* Here, m represents the minimum number of nodes from the two given trees.
* Space complexity : O(m). The depth of the recursion tree can go upto m
* in the case of a skewed tree. In average case, depth will be O(logm).
*/
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1 == null && root2 == null) {
return null;
}
if(root1 == null) {
return root2;
}
if(root2 == null) {
return root1;
}
root1.val += root2.val;
root1.left = mergeTrees(root1.left, root2.left);
root1.right = mergeTrees(root1.right, root2.right);
return root1;
}
}/**
* Time complexity : O(n). We traverse over a total of n nodes.
* Here, n refers to the smaller of the number of nodes in the two trees.
* Space complexity : O(n). The depth of stack can grow upto n in case of a skewed tree.
*/
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1 == null && root2 == null) {
return null;
}
if(root1 == null) {
return root2;
}
if(root2 == null) {
return root1;
}
Stack<TreeNode[]> stack = new Stack();
stack.push(new TreeNode[]{root1, root2});
while(!stack.isEmpty()) {
TreeNode[] t = stack.pop();
if(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 root1;
}
}