การรวมต้นไม้ไบนารีสองต้นใน C++

ภาพรวมปัญหา

เมื่อมีต้นไม้ไบนารีสองต้น และนำต้นหนึ่งมาทับอีกต้นหนึ่ง โหนดบางส่วนจะทับซ้อนกัน ในขณะที่บางส่วนไม่ทับซ้อน เราต้องรวมทั้งสองต้นให้กลายเป็นต้นไม้ไบนารีใหม่ โดยปฏิบัติตามกฎดังนี้:

• หากโหนดทั้งสองทับซ้อนกัน ให้นำค่าของโหนดทั้งสองมาบวกกันเป็นค่าใหม่ของโหนดที่รวมแล้ว
• หากมีเพียงโหนดเดียว (อีกโหนดเป็น null) ให้ใช้โหนดที่ไม่ใช่ null เป็นโหนดของต้นไม้ใหม่

ตัวอย่างภาพประกอบ

ผลลัพธ์หลังการรวม:

ขั้นตอนการแก้ปัญหา

ใช้ฟังก์ชัน mergeTrees() ที่รับโหนดสองโหนด (n1 และ n2) และทำงานดังนี้:

1. ถ้า n1 เป็น null และ n2 ไม่ใช่ null → คืนค่า n2
2. ถ้า n2 เป็น null และ n1 ไม่ใช่ null → คืนค่า n1
3. ถ้าทั้งคู่เป็น null → คืนค่า null
4. บวกค่าโหนด: n1->val += n2->val
5. เรียกใช้งานซ้ำสำหรับลูกซ้าย: n1->left = mergeTrees(n1->left, n2->left)
6. เรียกใช้งานซ้ำสำหรับลูกขวา: n1->right = mergeTrees(n1->right, n2->right)
7. คืนค่า n1

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) {
        val = data;
        left = right = NULL;
    }
};

void insert(TreeNode **root, int val) {
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()) {
        TreeNode *temp = q.front();
        q.pop();
        if(!temp->left) {
            temp->left = new TreeNode(val);
            return;
        } else {
            q.push(temp->left);
        }
        if(!temp->right) {
            temp->right = new TreeNode(val);
            return;
        } else {
            q.push(temp->right);
        }
    }
}

TreeNode *make_tree(vector<int> v) {
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i < v.size(); i++) {
        insert(&root, v[i]);
    }
    return root;
}

void tree_level_trav(TreeNode* root) {
    if (root == NULL) return;
    cout << "[";
    queue<TreeNode *> q;
    TreeNode *curr;
    q.push(root);
    q.push(NULL);
    while (q.size() > 1) {
        curr = q.front();
        q.pop();
        if (curr == NULL) {
            q.push(NULL);
        } else {
            if(curr->left) q.push(curr->left);
            if(curr->right) q.push(curr->right);
            if(curr->val == 0) {
                cout << "null, ";
            } else {
                cout << curr->val << ", ";
            }
        }
    }
    cout << "]" << endl;
}

class Solution {
public:
    TreeNode* mergeTrees(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 = mergeTrees(n1->left, n2->left);
        n1->right = mergeTrees(n1->right, n2->right);
        return n1;
    }
};

int main() {
    Solution ob;
    vector<int> v1 = {1, 3, 2, 5};
    vector<int> v2 = {2, 1, 3, NULL, 4, NULL, 7};
    TreeNode *root1 = make_tree(v1);
    TreeNode *root2 = make_tree(v2);
    root1 = ob.mergeTrees(root1, root2);
    tree_level_trav(root1);
    return 0;
}

ข้อมูลนำเข้า (Input)

[1,3,2,5] [2,1,3,null,4,null,7]

ผลลัพธ์ (Output)

[3, 4, 5, 5, 4, null, 7]