题目描述
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例：
输入:
Tree 1 Tree 2
1 2
/ /
3 2 1 3
/
5 4 7
输出:
合并后的树:
3
/
4 5
/
5 4 7
题目链接： https://leetcode-cn.com/problems/merge-two-binary-trees/
思路
使用递归来做：
- 如果两棵树有一个为空，则返回不为空的那棵树；
- 如果两棵树都不为空，则新节点的值为两棵树对应节点值之和。
代码如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
TreeNode* newRoot = nullptr;
newRoot = doMerge(t1, t2);
return newRoot;
}
TreeNode* doMerge(TreeNode* t1, TreeNode* t2){
if(t1==nullptr && t2==nullptr) return nullptr;
if(t1==nullptr && t2!=nullptr) return t2;
if(t1!=nullptr && t2==nullptr) return t1;
if(t1!=nullptr && t2!=nullptr){
TreeNode* root = new TreeNode(t1->val + t2->val);
root->left = doMerge(t1->left, t2->left);
root->right = doMerge(t1->right, t2->right);
return root;
}else{
return nullptr; // 这里return多少无关紧要，因为不会运行到这里
}
}
};
其实不用写成两个函数，这样写我觉得更易读。
- 时间复杂度：O(max(m, n))
m，n 分别为两颗树中的节点数。 - 空间复杂度：O(max(h1, h2))
h1，h2 分别为两棵树的树高。