Xóa nút lá có giá trị cho trước trong cây nhị phân (C++)

Cho một cây nhị phân và một giá trị nguyên target, xóa tất cả các nút lá có giá trị bằng target. Lưu ý: sau khi xóa nút lá, nếu nút cha trở thành nút lá và cũng có giá trị target, nó cũng phải bị xóa. Quá trình lặp lại cho đến khi không còn nút lá nào giá trị target.

Ví dụ minh họa

Thuật toán (Đệ quy hậu tự)

1. Định nghĩa hàm đệ quy removeLeafNodes(root, target).
2. Nếu root == nullptr → trả về nullptr.
3. Gọi đệ quy cho cây con trái và phải: left = removeLeafNodes(root->left, target), right = removeLeafNodes(root->right, target).
4. Cập nhật con trỏ: root->left = left, root->right = right.
5. Nếu sau khi xóa, nút hiện tại trở thành lá (left == nullptr && right == nullptr) VÀ root->val == target → trả về nullptr (xóa nút này).
6. Ngược lại trả về root.

Ví dụ code C++

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

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int data) : val(data), left(nullptr), right(nullptr) {}
};

// Hàm hỗ trợ tạo cây từ mảng (level order)
TreeNode* make_tree(vector<int> v) {
    if (v.empty()) return nullptr;
    TreeNode* root = new TreeNode(v[0]);
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (!q.empty() && i < v.size()) {
        TreeNode* curr = q.front(); q.pop();
        if (i < v.size() && v[i] != NULL) {
            curr->left = new TreeNode(v[i]);
            q.push(curr->left);
        }
        i++;
        if (i < v.size() && v[i] != NULL) {
            curr->right = new TreeNode(v[i]);
            q.push(curr->right);
        }
        i++;
    }
    return root;
}

// Duyệt level order để in cây
void tree_level_trav(TreeNode* root) {
    if (!root) return;
    cout << "[";
    queue<TreeNode*> q;
    q.push(root);
    q.push(nullptr);
    while (q.size() > 1) {
        TreeNode* curr = q.front(); q.pop();
        if (curr == nullptr) {
            q.push(nullptr);
        } else {
            if (curr->left) q.push(curr->left);
            if (curr->right) q.push(curr->right);
            cout << curr->val << ", ";
        }
    }
    cout << "]" << endl;
}

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

int main() {
    vector<int> v1 = {1,2,3,2,NULL,2,4}; // NULL đại diện cho nút rỗng
    TreeNode* root = make_tree(v1);
    Solution ob;
    tree_level_trav(ob.removeLeafNodes(root, 2));
    return 0;
}

Đầu vào / Đầu ra

Input:  [1,2,3,2,null,2,4] 2
Output: [1, 3, 4, ]

Giải thích

Cây ban đầu có các nút lá giá trị 2 bị xóa. Sau khi xóa, nút cha có giá trị 2 cũng trở thành lá và bị xóa tiếp. Kết quả chỉ còn lại các nút 1, 3, 4.