Problem:
Merge Two Binary Trees
Given two binary trees, we want to merge them into 1 tree.
The merge rule is: whenever the two trees' nodes overlap, the sum will be the new value, otherwise, the node with non-null value will be the new value.
For Example:
Given Tree 1 and Tree 2:
Tree 1 Tree 2
1 1
/ \ / \
3 2 2 3
/ \ \
5 4 7
Merged tree:
2
/ \
5 5
/ \ \
5 4 7
Solution:
We can solve this recursively. We don't need an extra tree, we can modify one of the trees in place.
Since we need to visit The time complexity will be O(M), the space cost will O(H). M is the number of nodes on the merged tree, H is the hight of the merged tree.
class Solution {
public static void main(String...args) {
Node root1 = new Node(1, new Node(3, new Node(5, null, null), null),
new Node(2, null, null));
Node root2 = new Node(1, new Node(2, null, new Node(4, null, null)),
new Node(3, null, new Node(7, null, null)));
printInorder(root1);
System.out.println();
printInorder(root2);
System.out.println();
printInorder(merge(root1, root2));
System.out.println();
}
private static Node merge(Node root1, Node root2) {
if(root1 == null)
return root2;
if(root2 == null)
return root1;
root1.value += root2.value;
root1.left = merge(root1.left, root2.left);
root1.right = merge(root1.right, root2.right);
return root1;
}
private static void printInorder(Node root) {
if(root == null) return;
printInorder(root.left);
System.out.print(root.value + " ");
printInorder(root.right);
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
public static void main(String...args) {
Node root1 = new Node(1, new Node(3, new Node(5, null, null), null),
new Node(2, null, null));
Node root2 = new Node(1, new Node(2, null, new Node(4, null, null)),
new Node(3, null, new Node(7, null, null)));
printInorder(root1);
System.out.println();
printInorder(root2);
System.out.println();
printInorder(merge(root1, root2));
System.out.println();
}
private static Node merge(Node root1, Node root2) {
if(root1 == null)
return root2;
if(root2 == null)
return root1;
root1.value += root2.value;
root1.left = merge(root1.left, root2.left);
root1.right = merge(root1.right, root2.right);
return root1;
}
private static void printInorder(Node root) {
if(root == null) return;
printInorder(root.left);
System.out.print(root.value + " ");
printInorder(root.right);
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
Time complexity O(M), the space cost O(H).
