题目链接

题目描述：

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

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

示例:
617合并二叉树 - 图1

解题思路

  题意要求我们合并两个二叉树，那么在某一结点考虑的问题只有三个：

  1. 两个树的该结点位置均为空；
  2. 两个树的该结点位置只有一个不为空；
  3. 两个树的该结点位置均不为空。

  套用先序遍历框架，将焦点集中在对当前结点的处理上即可解决问题，剩下的交给递归。这里可以考虑两种思路，一是另起炉灶新建一棵树，二是在某一个树上直接合并。

代码

  1. class Solution {
  2. public:
  3.     TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
  4.         if(!t1 && !t2)
  5.             return NULL;
  6.         else if(!t1 || !t2)
  7.             return t1 ? t1 : t2;
  8.         else{
  9.             TreeNode* root = new TreeNode(t1->val + t2->val);
  10.             root->left = mergeTrees(t1->left, t2->left);
  11.             root->right = mergeTrees(t1->right, t2->right);
  12.             return root;
  13.         }        
  14.     }
  15. };

如果有错误或者不严谨的地方，请务必给予指正，十分感谢。