代码随想录算法训练营第18天|654. 最大二叉树、617.合并二叉树、700. 二叉搜索树中的搜索、98.验证二叉搜索树-2.617.合并二叉树

题目链接：654. 最大二叉树
文档讲解： 代码随想录

class Solution(object):
    def mergeTrees(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: TreeNode
        """
        if not root1:
            return root2
        if not root2:
            return root1
        
        root1.val += root2.val
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)

        return root1

class Solution(object):
    def mergeTrees(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: TreeNode
        """
        if not root1:
            return root2
        if not root2:
            return root1
        #新建一个node
        node = TreeNode(0)
        node.val = root1.val + root2.val 
        node.left = self.mergeTrees(root1.left,root2.left)
        node.right = self.mergeTrees(root1.right, root2.right)
        return node

迭代法：

class Solution(object):
    def mergeTrees(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: TreeNode
        """
        if not root1: 
            return root2
        if not root2: 
            return root1
        
        queue = collections.deque()
        queue.append(root1)
        queue.append(root2)

        while queue:
            node1 = queue.popleft()
            node2 = queue.popleft()

            if node1.left and node2.left: 
                queue.append(node1.left)
                queue.append(node2.left)
            if node1.right and node2.right: 
                queue.append(node1.right)
                queue.append(node2.right)
            
            node1.val += node2.val
            if not node1.left and node2.left:
                node1.left = node2.left
            if not node1.right and node2.right:
                node1.right = node2.right
            
        return root1

class Solution(object):
    def mergeTrees(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: TreeNode
        """
        if not root1:
            return root2
        if not root2:
            return root1
        
        queue = deque()
        queue.append((root1, root2))

        while queue:
            node1, node2 = queue.popleft()
            node1.val += node2.val

            if node1.left and node2.left:
                queue.append((node1.left, node2.left))
            elif not node1.left:
                node1.left = node2.left
            
            if node1.right and node2.right:
                queue.append((node1.right, node2.right))
            elif not node1.right:
                node1.right = node2.right
        return root1