题目地址：

https://www.lintcode.com/problem/merge-two-binary-trees/description

合并两棵二叉树。合并的意思是，如果两棵树在相同位置都非空，则这个位置的值成为两棵树在此位置的节点之和。否则就是在此位置非空的那棵树在此位置的节点。

思路是递归。如果有一棵树空，则返回那个非空的，否则先合并树根，然后递归合并左右子树。代码如下：

public class Solution {
    /**
     * @param t1: the root of the first tree
     * @param t2: the root of the second tree
     * @return: the new binary tree after merge
     */
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        // Write your code here
        // 有一个是空，则返回非空的那个
        if (t1 == null) {
            return t2;
        } else if (t2 == null) {
            return t1;
        }
        
        // 合并树根
        t1.val += t2.val;
        // 递归合并左右子树
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }
}

class TreeNode {
    int val;
    TreeNode left, right;
    
    public TreeNode(int val) {
        this.val = val;
    }
}

时间复杂度 O ( n ) O(n) O(n)，空间 O ( h ) O(h) O(h)， n n n为两棵树节点数之和， h h h是两棵树高度更高者的高度。