合并二叉树

这是我参与11月更文挑战的第13天，活动详情查看：2021最后一次更文挑战

合并二叉树

问题描述

617. 合并二叉树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例：

输入：

       Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7    
复制代码

输出：

合并后的树:
           3
          / \
         4   5
        / \   \ 
       5   4   7
复制代码

分析问题

首先我们来看一下如何合并两个数组，例如对数组a=[1,3,2,5]和数组b=[2,1,3,4,7]进行合并，我们只需要遍历数组，将数组b的值合并到数组a中，然后返回a即可。对于二叉树来说，也和数组类似，我们遍历二叉树的每个节点，将对应节点合并即可。

对于二叉树的遍历，我们既可以使用深度优先搜索，也可以使用广度优先搜索。我们先来看一下如何使用深度优先搜索来求解。具体来说就是从根节点开始同时遍历两颗二叉树，并将其对应的节点进行合并。两个二叉树的对应节点可能存在以下三种情况，对于每种情况使用不同的合并方式。

• 如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空；
• 如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点；
• 如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和。

该节点合并完成后，我们接着递归的处理它的左右子节点，直到两棵树合并完成。

下面我们来看一下代码的实现。

class Solution:
    def mergeTrees(self, t1, t2):
        #如果一个节点为空，直接返回另一个
        if not t1:
            return t2
        if not t2:
            return t1
        #合并两个节点
        merged = TreeNode(t1.val + t2.val)
        #递归合并左、右子节点
        merged.left = self.mergeTrees(t1.left, t2.left)
        merged.right = self.mergeTrees(t1.right, t2.right)
        return merged
复制代码