今日算法：617，合并二叉树

class Solution { public: TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { // 终止条件：一个为空，直接返回另一个 if(root1 == nullptr) return root2; if(root2 == nullptr) return root1; // 当前节点值相加 TreeNode* node = new TreeNode(root1->val + root2->val); // 递归构建左右子树，挂载到当前节点 node->left = mergeTrees(root1->left, root2->left); node->right = mergeTrees(root1->right, root2->right); return node; } };

进行递归注意左右子树的存在；

class Solution { public: TreeNode*addtree(TreeNode*node1,TreeNode*node2) { if(node1==nullptr&&node2==nullptr) return node1;//终止条件 TreeNode*node=new TreeNode(0); if(node1&&node2) { node->val=node1->val+node2->val; } else if(node1&&node2==nullptr) { node->val=node1->val; } else if(node1==nullptr&&node2) { node->val=node2->val; } //遍历左右子树 //左 // if(node1->left||node2->left) // node->left=addtree(node1->left,node2->left); // if(node1->right||node2->right) // node->right=addtree(node->right,node2->right); if(node1 != nullptr && node2 != nullptr) node->left = addtree(node1->left, node2->left); else if(node1 != nullptr) node->left = addtree(node1->left, nullptr); else if(node2 != nullptr) node->left = addtree(nullptr, node2->left); // 右子树 if(node1 != nullptr && node2 != nullptr) node->right = addtree(node1->right, node2->right); else if(node1 != nullptr) node->right = addtree(node1->right, nullptr); else if(node2 != nullptr) node->right = addtree(nullptr, node2->right); return node; } TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { //前序遍历进行 return addtree(root1,root2); } };

理解递归的用法；

下面是非递归

class Solution { public: TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { //层序遍历 //迭代法 if(root1==nullptr) return root2; if(root2==nullptr) return root1; queue<TreeNode*> que; que.push(root1); 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!=nullptr&&node2->left!=nullptr) { que.push(node1->left); que.push(node2->left); } if(node1->right!=nullptr&&node2->right!=nullptr) { que.push(node1->right); que.push(node2->right); } //特殊情况 if(node1->left==nullptr&&node2->left) node1->left=node2->left; if(node1->right==nullptr&&node2->right) node1->right=node2->right; //因为本身返回的就是node1,所以不用对node1左右存在node2不存在做处理 } return root1; } };

使用一个队列而已

下面是使用3个队列进行解题

class Solution { public: TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { if (t1 == nullptr) { return t2; } if (t2 == nullptr) { return t1; } auto merged = new TreeNode(t1->val + t2->val); auto q = queue<TreeNode*>(); auto queue1 = queue<TreeNode*>(); auto queue2 = queue<TreeNode*>(); q.push(merged); queue1.push(t1); queue2.push(t2); while (!queue1.empty() && !queue2.empty()) { auto node = q.front(), node1 = queue1.front(), node2 = queue2.front(); q.pop(); queue1.pop(); queue2.pop(); auto left1 = node1->left, left2 = node2->left, right1 = node1->right, right2 = node2->right; if (left1 != nullptr || left2 != nullptr) { if (left1 != nullptr && left2 != nullptr) { auto left = new TreeNode(left1->val + left2->val); node->left = left; q.push(left); queue1.push(left1); queue2.push(left2); } else if (left1 != nullptr) { node->left = left1; } else if (left2 != nullptr) { node->left = left2; } } if (right1 != nullptr || right2 != nullptr) { if (right1 != nullptr && right2 != nullptr) { auto right = new TreeNode(right1->val + right2->val); node->right = right; q.push(right); queue1.push(right1); queue2.push(right2); } else if (right1 != nullptr) { node->right = right1; } else { node->right = right2; } } } return merged; } };

把两颗树进行放到两个队列中，进行相加到第三个队列，对左右子树进行处理，和我解释的递归解释那个写法很像；