题解 | #合并二叉树#

使用递归的方式解决该题，两个指针分别指向两棵树对应的同一结点，然后先序遍历两棵树，唯一需要相对于先序遍历改进的就是要判断下子节点是否存在。如果先序遍历过程中两棵树的结点都非空，那么把值相加，然后看两棵树的左子树是否存在，若都存在或都不存在则不用管，如果一棵树存在但是另一棵树不存在，那么就要给不存在的那个树new一个val为0的子树，类似的，看下右子树是否存在，然后加上，添加好子树后，分别去合并左右子树就可以了。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param t1 TreeNode类 
# @param t2 TreeNode类 
# @return TreeNode类
#
class Solution:
    def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode:
        # write code here
        # 先序遍历解决该问题，以tree1作为主要的树
        self.pretra(t1,t2)
        return t1

    def pretra(self,t1,t2):
        if t1!=None and t2!=None:
            t1.val = t1.val+t2.val
            if t1.left ==None and t2.left !=None:
                t1.left = TreeNode(0)
            elif t2.left ==None and t1.left !=None:
                t2.left = TreeNode(0)
            self.pretra(t1.left , t2.left)
            if t1.right ==None and t2.right != None:
                t1.right = TreeNode(0)
            elif t2.right ==None and t1.right !=None:
                t2.right = TreeNode(0)
            self.pretra(t1.right , t2.right)
        else:
            return
            
def preord(root):
    if root:
        print(root.val)
        preord(root.left)
        preord(root.right)

root1 = TreeNode(1)
root1.left = TreeNode(3)
root1.left.left = TreeNode(5)
root1.right = TreeNode(2)

root2 = TreeNode(2)
root2.left = TreeNode(1)
root2.left.right = TreeNode(4)
root2.right = TreeNode(3)
root2.right.right = TreeNode(7)
root = Solution().mergeTrees(root1,root2)
preord(root)