题干:
代码(递归实现):
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {//前序好理解,直接将树覆盖到另一个上面
if(root1 == NULL)return root2;//当前遍历节点为空的话就让另一个的值覆盖过来
if(root2 == NULL)return root1;
root1 -> val += root2 -> val;
root1 -> left = mergeTrees(root1 -> left, root2 -> left);
root1 -> right = mergeTrees(root1 -> right, root2 -> right);
return root1;
}
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2){//重新定义一棵树
if(root1 == NULL)return root2;
if(root2 == NULL)reutrn root1;
TreeNode* node = new TreeNode(0);
node -> left = mergeTrees(root1-> left, root2->left);
node -> right = mergeTrees(root1-> right, root2-> right);
return node;
代码(迭代实现):在判断二叉树是否对称时涉及到了判断两个子树,用到了队列,那么处理两个树就使用队列。
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {//这里也是将树2覆盖到树1上
if(root1 == NULL)return root2;
if(root2 == NULL)return root1;
queue<TreeNode*>que;
if(root1 != NULL)que.push(root1);
if(root2 != NULL)que.push(root2);
while(!que.empty()){
TreeNode* node1 = que.front();
que.pop();
TreeNode* node2 = que.front();
que.pop();
node1-> val += node2->val;
if(node1->left && node2-> left){
que.push(node1->left);
que.push(node2->left);
}
if(node1-> right && node2->right){
que.push(node1->right);
que.push(node2->right);
}
if(!node1->left && node2->left){//都是判断树1左右是否空,空就让树2的左右覆盖,不会考虑树2
node1->left = node2->left;
}
if(!node1->right && node2->right){
node1->right = node2->right;
}
}
return root1;
}