給定兩個(gè)二叉樹，想象當(dāng)你將它們中的一個(gè)覆蓋到另一個(gè)上時(shí)，兩個(gè)二叉樹的一些節(jié)點(diǎn)便會(huì)重疊。

你需要將他們合并為一個(gè)新的二叉樹。合并的規(guī)則是如果兩個(gè)節(jié)點(diǎn)重疊，那么將他們的值相加作為節(jié)點(diǎn)合并后的新值，否則不為 NULL 的節(jié)點(diǎn)將直接作為新二叉樹的節(jié)點(diǎn)。

示例 1:
輸入:
Tree 1????Tree 2
?1 ??????2
?/ \ ?????? / \
?3?2 ?????1?3
?/ ??????? \ ??\
5???????? 4??7
輸出:
合并后的樹:
??3
??/ ?\
?4??5
?/ ?\ ??\
5?4???7

注意: 合并必須從兩個(gè)樹的根節(jié)點(diǎn)開始。
解題思路:一開始沒弄懂啥意思，看了別人的代碼發(fā)現(xiàn)思路很簡(jiǎn)單，將兩棵樹同步遍歷，如果兩個(gè)節(jié)點(diǎn)均有值則相加，否則返回另一個(gè)節(jié)點(diǎn)的值。

class Solution {
   public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if(t1 == null)
            return t2;
        if(t2 == null)
            return t1;
        TreeNode ans = new TreeNode(t1.val + t2.val);
        ans.left = mergeTrees(t1.left,t2.left);
        ans.right = mergeTrees(t1.right,t2.right);
        return ans;
    }
}

復(fù)雜度分析:
時(shí)間復(fù)雜度:O(N);
空間復(fù)雜度:O(N)