Xóa nút lá trên đường đi gốc->lá có độ dài < K trong cây nhị phân bằng C++

Cho cây nhị phân và số K. Xóa các nút lá nằm trên đường đi từ gốc có độ dài < K. Sau khi xóa, nút cha có thể trở thành lá mới và cũng bị xóa nếu đường đi mới < K. Lặp cho đến ổn định.

Cách tiếp cận: Duyệt hậu thứ tự (Post-order) + Đệ quy

Duyệt hậu thứ tự (con trước, cha sau). Hàm đệ quy trimmer(node, len, K):

• Đệ quy con trái/phải với len+1.
• Nếu nút hiện tại là lá (!left && !right) và len < K → xóa (trả về NULL).
• Ngược lại trả về nút hiện tại.

Ví dụ

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

struct Node { char data; Node *left, *right; };
Node* newNode(char data) {
    Node* node = new Node;
    node->data = data; node->left = node->right = NULL;
    return node;
}

Node* trimmer(Node* root, int len, int k) {
    if (!root) return NULL;
    root->left = trimmer(root->left, len + 1, k);
    root->right = trimmer(root->right, len + 1, k);
    if (!root->left && !root->right && len < k) {
        delete root; return NULL;
    }
    return root;
}

Node* trim(Node* root, int k) { return trimmer(root, 1, k); }

void printInorder(Node* root) {
    if (root) { printInorder(root->left); cout << root->data << " "; printInorder(root->right); }
}

int main() {
    int k = 4;
    Node* root = newNode('A');
    root->left = newNode('B'); root->right = newNode('G');
    root->left->left = newNode('C'); root->left->right = newNode('D');
    root->left->left->left = newNode('E'); root->left->left->right = newNode('F');
    root->right->left = newNode('H'); root->right->right = newNode('I');
    printInorder(root); cout << "\n";
    root = trim(root, k);
    printInorder(root);
    return 0;
}

Kết quả

E C F B D A H G I  E C F B A

Giải thích

Duyệt hậu thứ tự đảm bảo con được xử lý trước cha. Nút lá có độ dài đường đi < K bị xóa. Cha trở thành lá mới → tiếp tục kiểm tra ở bước backtrack.

Kết luận

Xóa nút lá trên đường đi gốc->lá độ dài < K bằng duyệt hậu thứ tự đệ quy O(N). Code C++ mẫu.