617合并二叉树

题目链接

题目描述：

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

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

示例:

解题思路

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

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

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

代码

cpp

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(!t1 && !t2)
            return NULL;
        else if(!t1 || !t2)
            return t1 ? t1 : t2;
        else{
            TreeNode* root = new TreeNode(t1->val + t2->val);
            root->left = mergeTrees(t1->left, t2->left);
            root->right = mergeTrees(t1->right, t2->right);
            return root;
        }        
    }
};

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