การลบโหนดใบที่มีค่าเท่ากับเป้าหมายในต้นไม้แบบทวิภาค C++

สมมติว่าเรามีต้นไม้แบบทวิภาค (binary tree) และค่าเป้าหมายเป็นจำนวนเต็ม เราต้องลบโหนดใบ (leaf nodes) ทั้งหมดที่มีค่าเท่ากับเป้าหมาย จำไว้ว่าเมื่อลบโหนดใบที่มีค่าเป้าหมายแล้ว หากโหนดพาเรนต์กลายเป็นโหนดใบและมีค่าเท่ากับเป้าหมาย ก็ต้องลบด้วย (ทำซ้ำจนกว่าจะไม่สามารถลบได้อีก)

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

1. กำหนดเมธอดเรียกซ้ำ (recursive) ชื่อ remLeaf() ที่รับ root และ target
2. ถ้า root เป็น null ให้คืนค่า null
3. left := remLeaf(left ของ root, target)
4. right := remLeaf(right ของ root, target)
5. ถ้า left เป็น null และ right เป็น null และค่าของ root เท่ากับ target ให้คืนค่า null
6. left ของ root := left
7. right ของ root := right
8. คืนค่า root

ตัวอย่างโค้ด (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) {
            if(val != NULL) temp->left = new TreeNode(val);
            else temp->left = new TreeNode(0);
            return;
        } else q.push(temp->left);
        
        if(!temp->right) {
            if(val != NULL) temp->right = new TreeNode(val);
            else temp->right = new TreeNode(0);
            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;
    q.push(root); q.push(NULL);
    while(q.size() > 1) {
        TreeNode *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 || curr == NULL) cout << "null, ";
            else cout << curr->val << ", ";
        }
    }
    cout << "]" << endl;
}

class Solution {
public:
    TreeNode* removeLeafNodes(TreeNode* root, int target) {
        if(!root || root->val == 0) return NULL;
        TreeNode* left = removeLeafNodes(root->left, target);
        TreeNode* right = removeLeafNodes(root->right, target);
        if(!left && !right && root->val == target) return NULL;
        root->left = left;
        root->right = right;
        return root;
    }
};

int main() {
    vector<int> v1 = {1,2,3,2,NULL,2,4};
    TreeNode *root = make_tree(v1);
    Solution ob;
    tree_level_trav(ob.removeLeafNodes(root, 2));
    return 0;
}

อินพุต

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

เอาต์พุต

[1, 3, 4, ]