题解 | #合并二叉树#

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param t1 TreeNode类 
# @param t2 TreeNode类 
# @return TreeNode类
#
import queue
class Solution:
    # def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode:
    #     # write code here
    #     """
    #     method_1: 递归前序遍历
    #     步骤：
    #     step1: 判断t1 和t2 是否为空， 若为空，则用另一个替代； 若都为空，返回值为空
    #     step2: 依据谦虚遍历的特点，有限访问根节点，将两个根点的值相加，并创建新树】
    #     step3: 两颗子树同步进入左子树和右子树
    #     """
    #     if not t1:
    #         return t2
    #     elif not t2:
    #         return t1
        
    #     head = TreeNode(t1.val + t2.val)
    #     head.left = self.mergeTrees(t1.left, t2.left)
    #     head.right = self.mergeTrees(t1.right, t2.right)
    #     return head
        
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        """
        method_2: 非递归思想，使用队列
        步骤： 
        step1: t1 和 t2 判空， 若为空则用另一代替； 若两者周空，返回值也为空
        step2:  使用三个辅助队列，第一个队列q用于暂存合并后的二叉树的层次遍历节点，第二个队列q1 用于暂存t1的层次遍历节点， 第三个队列q2 用于暂存t2 的层次遍历节点；
        step3: 两棵树同步层次遍历， 现将根节点加入到队列中，同时根节点优先合并‘
        step4: 每次从队列分别弹出一个元素，判断分别二者的左右子节点是否存在，若是都存在，则相加合并，若是只存在一个则链接该存在的节点，若是都不存在，则链接空
        """
        if not t1:
            return t2
        if not t2:
            return t1
        # 合并根节点
        head = TreeNode(t1.val + t2.val) 
        # 连接后的树的层次遍历节点
        q = queue.Queue() 
        # 分别存两棵树的层次遍历节点
        q1 = queue.Queue() 
        q2 = queue.Queue()
        q.put(head)
        q1.put(t1)  
        q2.put(t2)
        while not q1.empty() and not q2.empty():
            node = q.get()
            node1 = q1.get()
            node2 = q2.get()
            left1 = node1.left
            left2 = node2.left
            right1 = node1.right
            right2 = node2.right
            # 两个左节点都存在
            if left1 or left2:  
                if left1 and left2:
                    left = TreeNode(left1.val + left2.val)
                    node.left = left
                    # 新节点入队列
                    q.put(left)  
                    q1.put(left1)
                    q2.put(left2)
                # 只连接一个节点
                elif left1: 
                    node.left = left1
                elif left2:
                    node.left = left2
            if right1 or right2:
                # 两个右节点都存在
                if right1 and right2: 
                    right = TreeNode(right1.val + right2.val)
                    node.right = right
                    # 新节点入队列
                    q.put(right)
                    q1.put(right1)
                    q2.put(right2)
                # 只连接一个节点
                elif right1:  
                    node.right = right1
                else:
                    node.right = right2
        return head
		buds