617. 合并二叉树

一、题目描述

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

输入: 
    Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
         3
        / \
       4   5
      / \   \ 
     5   4   7

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-binary-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

注意: 合并必须从两个树的根节点开始。

二、思路 & 代码实现

（1）思路描述

• 首先我选择使用层次遍历的方式来写这道题。
• 其次是将 Tree2 合并到 Tree1 上边，作为一颗新的二叉树返回
• 方向确定了，接下来就是程序实现的设计了
• 首先判断传入函数的 t1 、t2是否为None，t1为None返回t2，t2为None返回t1，都为None返回None。t1和t2都不为None，接着往下走
• 定义两个队列dequeue1保存Tree1的层次遍历节点，dequeue2保存Tree2的遍历节点。首先将t1、t2分别添加到dequeue1和dequeue2
• 接着循环遍历往下走：
  • 进入循环首先实现根节点的值的更新
  • 接下来每一次遍历对节点左右子树进行判断
    • t1和t2左右子树都存在，则分别添加到队列中
    • 如果t1的左子树或右子树存在，t2的左子树或右子树不存在。这时是不需要做任何操作的
    • 如果t2的左子树或右子树存在，t1的左子树或右子树不存在。那么需要将t2的左子树或者右子树添加到t1的
• 最后返回t1即可。

（2）代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        '''层次遍历'''

        # 1、首先对t1和t2进行判断
        if t1 and not t2:
            return t1
        elif not t1 and t2:
            return t2
        elif not t1 and not t2:
            return 

        # 2、定义队列保存遍历节点
        dequeue1 = []
        dequeue2 = []

        dequeue1.append(t1)
        dequeue2.append(t2)

        while dequeue1 and dequeue2:
            d1 = dequeue1.pop(0)
            d2 = dequeue2.pop(0)
            # 对根的值进行更新
            d1.val = d1.val + d2.val

            # 左右子树判断
            if d1.left and d2.left:
                dequeue1.append(d1.left)
                dequeue2.append(d2.left)
            elif d2.left:
                d1.left = d2.left

            if d1.right and d2.right:
                dequeue1.append(d1.right)
                dequeue2.append(d2.right)

            elif d2.right:
                d1.right = d2.right

         return t1

（3）表现

运行时间	表现	内存消耗	表现
100ms	91.61%	14.3MB	88.39%