1 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.
 2 
 3 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.
 4 
 5 Example 1:
 6 
 7 Input: 
 8     Tree 1                     Tree 2                  
 9           1                         2                             
10          / \                       / \                            
11         3   2                     1   3                        
12        /                           \   \                      
13       5                             4   7                  
14 Output: 
15 Merged tree:
16          3
17         / \
18        4   5
19       / \   \ 
20      5   4   7
21  
22 
23 Note: The merging process must start from the root nodes of both trees.
24 
25 来源：力扣（LeetCode）
26 链接：https://leetcode-cn.com/problems/merge-two-binary-trees
27 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

看到题目第一时间考虑使用层序遍历，想绕开递归。对于设计递归算法有种莫名的排斥，虽然总是看到“递归简化程序”，程序是简化了，但是设计程序并未简化。

设计一个递归函数要有三个要点：

1.递归什么时候退出？

这个情况一般是一个具体问题最“简单”的情形，拿二叉树来说，一般就是当前指针为空指针。

2.一次递归调用需要做什么？

3.当前调用给上一级调用返回什么？

2和3通常需要一起考虑。递归要退出不陷入栈溢出，那么一定有返回，可以没有返回值。

递归的返回值可以由问题确定，比如求二叉树深度，返回的一般就是深度。

有时候考虑问题不清楚，会陷入返回两个参数的情形，这个时候可以尝试把问题分解，添加子函数实现一部分逻辑。

或者设计一个返回值结构体，拿来作返回。//待添加例子。。。

有时候问题要求的结果不是数值，而是要求实现某一过程，这个时候就可以没有返回值，比如我这道题的一个实现。

综上，递归是一定要有退出递归的出口，递归的过程和返回通常需要一起考虑，递归可以不返回值。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 
12 public:
13     void recursive(TreeNode* &t1, TreeNode* &t2){
14         if (t1==nullptr || t2==nullptr){
15             if (t2)
16                 t1=t2;
17             return;
18         }
19         t1->val+=t2->val;
20 
21         recursive(t1->left,t2->left);
22         recursive(t1->right,t2->right);
23     }
24     TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
25         recursive(t1,t2);
26         return t1;
27     }
28 };

在这个实现里，没有新建树，把树1作为最终的树，在它身上修改。设计了一个子函数来实现merge，这个函数就没有返回值，它只是遍历两棵树。

最后只需要返回t1指针即可。