【解题思路】：选择其中一棵树(如左边root1的树)作为最终输出的树，然后将另外一棵树叠加到这棵树上。 【注意事项】：遍历到输出树root1节点为空，而叠加树root2节点非空时，直接把root2作为root1即可，但需要额外传参才能完成
- root1的父节点；
- root1是父节点的左子树还是右子树
DFS
代码语言：javascript复制/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void dfs(TreeNode* parent1, TreeNode* root1, TreeNode* root2, string str) {
/** 把左边root1作为最终输出的树**/
// 1.if 两节点都空 or 仅root2为空
if ((!root1 && !root2) || (root1 && !root2)) return;
// 2.if 仅root1为空
if (!root1 && root2) {
( (str == "left") ? parent1->left : parent1->right ) = root2;
return;
// 3.root1和root2均非空
} else root1->val = root2->val;
dfs(root1, root1->left, root2->left, "left");
dfs(root1, root1->right, root2->right, "right");
}
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (!root1 && root2) return root2;
dfs(root1, root1, root2, "");
return root1;
}
};由于没有额外创建树，只是在其中一棵树上进行叠加，因此相对减少内存消耗，结果如下
