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

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

    示例 1:

    输入:
    Tree 1 Tree 2
    1 2
    / \ / \
    3 2 1 3
    / \ \
    5 4 7
    输出:
    合并后的树:
    3
    / \
    4 5
    / \ \
    5 4 7
    注意: 合并必须从两个树的根节点开始。

    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. public:
    12.     // 深度优先递归
    14.     TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) 
    15.     {
    16.         if (t1 == nullptr)
    17.             return t2;
    18.         if (t2 == nullptr)
    19.             return t1;
    21.         // 方法I: 中序遍历方式
    22.         TreeNode * merged = new TreeNode(t1->val + t2->val);    // 中
    23.         merged->left = mergeTrees(t1->left, t2->left);          // 左
    24.         merged->right = mergeTrees(t1->right, t2->right);       // 右
    27.         // 方法II: 前序遍历方式
    28.         TreeNode * merged = new TreeNode(0);
    29.         merged->left = mergeTrees(t1->left, t2->left);          // 左
    30.         merged->val += (t1->val + t2->val);                     // 中
    31.         merged->right = mergeTrees(t1->right, t2->right);       // 右
    34.         // 方法III: 后序遍历方式
    35.         TreeNode * merged = new TreeNode(0);
    36.         merged->left = mergeTrees(t1->left, t2->left);          // 左
    37.         merged->right = mergeTrees(t1->right, t2->right);       // 右
    38.         merged->val += (t1->val + t2->val);                     // 中
    39.         return merged;
    40.     }
    41. };

    欢迎交流，批评指正！