題目描述：

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

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

示例?1:

輸入:

Tree 1? ? ? ? ? ? ? ? ? ? Tree 2? ? ? ? ? ? ? ? ?

? ? ? ? ? 1? ? ? ? ? ? ? ? ? ? ? ? 2? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? / \? ? ? ? ? ? ? ? ? ? ? / \? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? 3? 2? ? ? ? ? ? ? ? ? ? 1? 3? ? ? ? ? ? ? ? ? ? ? ?

? ? ? /? ? ? ? ? ? ? ? ? ? ? ? ? \? \? ? ? ? ? ? ? ? ? ? ?

? ? ? 5? ? ? ? ? ? ? ? ? ? ? ? ? ? 4? 7? ? ? ? ? ? ? ? ?

輸出:

合并后的樹(shù):

? ? 3

? ? / \

? 4? 5

? / \? \

5? 4? 7

注意:?合并必須從兩個(gè)樹(shù)的根節(jié)點(diǎn)開(kāi)始。

解法：

遞歸：

我們可以對(duì)這兩棵樹(shù)同時(shí)進(jìn)行前序遍歷，并將對(duì)應(yīng)的節(jié)點(diǎn)進(jìn)行合并。在遍歷時(shí)，如果兩棵樹(shù)的當(dāng)前節(jié)點(diǎn)均不為空，我們就將它們的值進(jìn)行相加，并對(duì)它們的左孩子和右孩子進(jìn)行遞歸合并；如果其中有一棵樹(shù)為空，那么我們返回另一顆樹(shù)作為結(jié)果；如果兩棵樹(shù)均為空，此時(shí)返回任意一棵樹(shù)均可（因?yàn)槎际强眨?/p>