สมมติว่าเรามีต้นไม้ไบนารีสองต้น และพิจารณาว่าเมื่อเราใส่หนึ่งในต้นไม้เหล่านั้นเพื่อคลุมอีกต้นหนึ่ง โหนดของต้นไม้สองต้นจะซ้อนทับกันในขณะที่อีกต้นซ้อนทับกัน เราต้องรวมพวกมันเข้าเป็นไบนารีทรีใหม่ กฎการผสานจะเป็นเช่นนั้น ถ้าสองโหนดซ้อนทับกัน ให้รวมค่าของโหนดเป็นค่าใหม่ของโหนดที่ผสาน มิฉะนั้น โหนดที่ไม่ว่างจะถูกใช้เป็นโหนดของทรีใหม่
ดังนั้นหากต้นไม้เป็น −
จากนั้นผลลัพธ์จะเป็น −
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- เมธอดคือ Solve() ใช้โหนดทรีสองโหนด n1 และ n2 แบบนี้สิ
- หาก n1 ว่างเปล่า และ n2 ไม่ว่างเปล่า ให้คืนค่า n2 มิฉะนั้น เมื่อ n2 ว่างเปล่า และ n1 ไม่ว่างเปล่า ให้คืนค่า n1 และเมื่อทั้งคู่มีค่าว่าง ให้คืนค่า null
- ค่าของ n1 :=ค่าของ n1 + ค่าของ n2
- ซ้ายของ n1 :=แก้ (ซ้ายของ n1 ซ้ายของ n2)
- ขวาของ n1 :=แก้ (ขวาของ n1 ขวาของ n2)
- คืน n1
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int v){
val = v;
left = right = NULL;
}
};
void inord(TreeNode *root) {
if (root != NULL) {
inord(root->left);
cout << root->val << " ";
inord(root->right);
}
}
class Solution {
public:
TreeNode* solve(TreeNode* n1, TreeNode* n2) {
if(!n1 && n2)
return n2;
else if(!n2 && n1)
return n1;
else if(!n1 && !n2)
return NULL;
n1->val+=n2->val;
n1->left = solve(n1->left,n2->left);
n1->right = solve(n1->right,n2->right);
return n1;
}
};
main(){
TreeNode *root1 = new TreeNode(1);
root1->left = new TreeNode(3);
root1->right = new TreeNode(2);
root1->left->left = new TreeNode(5);
TreeNode *root2 = new TreeNode(2);
root2->left = new TreeNode(1);
root2->right = new TreeNode(3);
root2->left->right = new TreeNode(4);
root2->right->right = new TreeNode(7);
Solution ob;
TreeNode *root_res = ob.solve(root1, root2);
inord(root_res);
} อินพุต
TreeNode *root1 = new TreeNode(1); root1->left = new TreeNode(3); root1->right = new TreeNode(2); root1->left->left = new TreeNode(5); TreeNode *root2 = new TreeNode(2); root2->left = new TreeNode(1); root2->right = new TreeNode(3); root2->left->right = new TreeNode(4); root2->right->right = new TreeNode(7);
ผลลัพธ์
5 4 4 3 5 7
