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

ภาพรวมปัญหา

ให้ต้นไม้ไบนารีสองต้น ต้องการรวม (merge) เป็นต้นไม้เดียว กฎ: โหนดทับกัน → บวกค่า, โหนดไม่ทับกัน → นำมาใช้ต่อ

ตัวอย่าง

Tree 1: Tree 2: Merged:

    1              2              3
   / \            / \            / \
  3   2          1   3          4   5
 /              \   \            / \   \
5                4   7          5   4   7

Inorder traversal: 5 4 4 3 5 7

แนวทางแก้ปัญหา (Recursive DFS)

1. ฟังก์ชัน mergeTrees(n1, n2)
2. Base cases:
• n1==null && n2!=null → return n2
• n1!=null && n2==null → return n1
• n1==null && n2==null → return null
3. n1->val += n2->val (บวกค่า)
4. n1->left = mergeTrees(n1->left, n2->left)
5. n1->right = mergeTrees(n1->right, n2->right)
6. return n1

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

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

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

void inorder(TreeNode *root) {
    if (root) {
        inorder(root->left);
        cout << root->val << " ";
        inorder(root->right);
    }
}

class Solution {
public:
    TreeNode* solve(TreeNode* n1, TreeNode* n2) {
        if (!n1 && n2) return n2;
        if (!n2 && n1) return n1;
        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;
    }
};

int 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 *merged = ob.solve(root1, root2);
    inorder(merged);
    return 0;
}

ผลลัพธ์

5 4 4 3 5 7

ความซับซ้อน

• เวลา: O(min(N₁, N₂)) — เยี่ยมชมเฉพาะโหนดที่ทับกัน
• พื้นที่: O(min(H₁, H₂)) — recursion stack

แนวทาง Iterative (BFS/DFS with Stack)

หลีกเลี่ยง recursion stack overflow สำหรับต้นไม้ลึกมาก

TreeNode* mergeTrees_iterative(TreeNode* root1, TreeNode* root2) {
    if (!root1) return root2;
    if (!root2) return root1;
    
    stack> st;
    st.push({root1, root2});
    
    while (!st.empty()) {
        auto [n1, n2] = st.top(); st.pop();
        n1->val += n2->val;
        
        if (n1->left && n2->left) st.push({n1->left, n2->left});
        else if (!n1->left) n1->left = n2->left;
        
        if (n1->right && n2->right) st.push({n1->right, n2->right});
        else if (!n1->right) n1->right = n2->right;
    }
    return root1;
}

ข้อควรระวัง

• โค้ดแก้ไขต้นไม้ต้นแรก (root1) ในที่เดียว (in-place) — ต้องการเก็บต้นไม้เดิมต้อง clone ก่อน
• LeetCode 617 "Merge Two Binary Trees"