題目

難度：★★☆☆☆
類型：二叉樹

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

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

示例

輸入:
Tree 1 Tree 2
1 2
/ \ /
3 2 1 3
/ \
5 4 7
輸出:
合并后的樹:
3
/
4 5
/ \
5 4 7
注意: 合并必須從兩個樹的根節(jié)點(diǎn)開始。

解答

設(shè)計(jì)融合函數(shù)，融合兩棵樹：

1. 如果輸入的兩棵樹均為空，返回空即可，如果輸入的兩棵樹只有一棵為空，返回非空樹；

2. 如果兩棵樹均不為空，首先融合當(dāng)前結(jié)點(diǎn)，然后將左右子樹融合后掛在當(dāng)前結(jié)點(diǎn)上。

class Solution:
    def mergeTrees(self, t1, t2):
        if not t1:                                          # 如果t1為空
            return t2                                       # 返回t2
        if not t2:                                          # 如果t2為空
            return t1                                       # 返回t1
        root = TreeNode(t1.val + t2.val)                    # 獲得當(dāng)前結(jié)點(diǎn)
        root.left = self.mergeTrees(t1.left, t2.left)       # 融合左子樹
        root.right = self.mergeTrees(t1.right, t2.right)    # 融合右子樹
        return root                                         # 返回融合的樹

這里有個更加高效的版本：

class Solution:
    def mergeTrees(self, t1, t2):
        if t1 and t2:                                               # 如果輸入的兩個結(jié)點(diǎn)均不為空
            t1.val += t2.val                                        # 結(jié)點(diǎn)值相加
            t1.left = self.mergeTrees(t1.left, t2.left)             # 合并左子樹
            t1.right = self.mergeTrees(t1.right, t2.right)          # 合并右子樹
            return t1                                               # 返回t1
        return t1 or t2      

如有疑問或建議，歡迎評論區(qū)留言~