617. Merge Two Binary Trees

题目：

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

给两个二叉树想要合并，有一些结点会重叠而有一些不会，现在想把重叠的结点值变为两者值相加，不重叠的直接用，构建出新的树

Example 1:

Input: 	Tree 1                     Tree 2                            1                         2                                      / \                       / \                                    3   2                     1   3                               /                           \   \                            5                             4   7                  Output: Merged tree:	     3	    / \	   4   5	  / \   \ 	 5   4   7

 

Note: The merging process must start from the root nodes of both trees.

合并都从两个二叉树根部开始

思路：

考察的就是二叉树的遍历，遍历每个结点然后如果重叠（两个二叉树结点都不为空）新结点值便为两者和，不重叠（只有一个结点为空）新结点值为不为空的值，全为空到达底部返跳出。按照这个逻辑进行迭代

联想：二叉树遍历方式有深度优先和广度优先，深度（纵向）优先在Python中一般使用列表，广度优先（横向）一般使用迭代

 

结果：

# Definition for a binary tree node. # class TreeNode(object): #     def __init__(self, x): #         self.val = x #         self.left = None #         self.right = None class Solution(object):     def mergeTrees(self, t1, t2):         """         :type t1: TreeNode         :type t2: TreeNode         :rtype: TreeNode         """         # 结点都为空时         if t1 is None and t2 is None:             return         # 只有一个结点为空时         if t1 is None:             return t2         if t2 is None:             return t1         # 结点重叠时         t1.val += t2.val         # 进行迭代         t1.right = self.mergeTrees(t1.right, t2.right)         t1.left = self.mergeTrees(t1.left, t2.left)         return t1