Merge Two Binary Trees

Problem

Merge Two Binary Trees

Approach

We can use recursion method to solve this problem. Firstly, we can traverse the tree in the preorder fashion. At every step, we check if any one of them is null. If so, we can just return themselves immediatally. Otherwise, we can new a TreeNode or use T1/T2 to combine both of them. Then, we can continue call the original method Merge to deal with their left and right children. At the end, the merged tree is returned.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if(t1 == null){
            return t2;
        }
        if(t2 == null){
            return t1;
        }
        TreeNode r = new TreeNode(t1.val + t2.val);
        r.left = mergeTrees(t1.left, t2.left);
        r.right = mergeTrees(t1.right, t2.right);
        return r;
    }
}