โปรแกรมตัดกิ่งต้นไม้ไบนารี (Prune Binary Tree) ใน C++

ภาพรวมปัญหา

ให้ต้นไม้ไบนารีที่โหนดมีค่า 0 หรือ 1 ต้องการตัดกิ่งย่อย (subtree) ที่ไม่มีค่า 1 ออกทั้งหมด

ตัวอย่าง

ต้นไม้ต้นฉบับ → หลังตัดกิ่งที่ไม่มี 1

แนวทางแก้ปัญหา (Post-order DFS)

1. ฟังก์ชัน recursive pruneTree(TreeNode* node)
2. ถ้า node เป็น null คืนค่า null
3. เรียก recursion บน left และ right child
4. อัปเดต left และ right ด้วยผลลัพธ์จาก recursion
5. ถ้า left==null และ right==null และ node->val==0 → คืนค่า null (ตัดทิ้ง)
6. มิฉะนั้น คืนค่า node

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

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

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

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

class Solution {
public:
    TreeNode* pruneTree(TreeNode* node) {
        if (!node) return NULL;
        node->left = pruneTree(node->left);
        node->right = pruneTree(node->right);
        if (!node->left && !node->right && !node->val) {
            return NULL;
        }
        return node;
    }
};

int main() {
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(1);
    root->right = new TreeNode(0);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(1);
    root->right->left = new TreeNode(0);
    root->right->right = new TreeNode(1);
    root->left->left->left = new TreeNode(0);
    
    Solution ob;
    inorder(ob.pruneTree(root));
    return 0;
}

ผลลัพธ์

1, 1, 1, 1, 0, 1,

การทำงานของอัลกอริทึม

• Post-order traversal: ประมวลผลลูกก่อน แล้วค่อยประมวลผลโหนดปัจจุบัน
• โหนดใบ (leaf) ที่มีค่า 0 จะถูกตัดทิ้ง (คืนค่า null ให้ parent)
• โหนดภายในที่กลายเป็นใบและมีค่า 0 ก็จะถูกตัดทิ้งเช่นกัน
• โหนดที่มีค่า 1 จะไม่ถูกตัดเลย

ความซับซ้อน

• เวลา: O(N) — เยี่ยมชมแต่ละโหนด 1 ครั้ง
• พื้นที่: O(H) — recursion stack โดย H = ความสูงของต้นไม้ (O(N) worst case, O(log N) balanced)

การประยุกต์ใช้

เทคนิคนี้ใช้ในการลดขนาดต้นไม้ตัดสินใจ (Decision Tree Pruning), Game Tree Pruning (Alpha-Beta), และการทำความสะอาดข้อมูลโครงสร้างต้นไม้