예를 들어 트리가 주어지면 주어진 k보다 길이가 짧은 경로의 리프 노드를 제거해야 합니다.

입력 -

K = 4.

출력 -

설명

The paths were :
1. A -> B -> C -> E length = 4
2. A -> B -> C -> F length = 4
3. A -> B -> D length = 3
4. A -> G -> H length = 3
5. A -> B -> I length = 3
Now as you can see paths 3, 4, 5 have length of 3 which is less than given k so we remove the leaf nodes of these paths i.e. D, H, I.
Now for path 4 and 5 when H and I are removed we notice that now G is also a leaf node with path length 2 so we again remove node G and here our program ends.

우리는 후순위 형식으로 트리를 탐색할 것입니다. 그런 다음 경로 길이가 K보다 작은 경우 리프 노드를 제거하는 재귀 함수를 만듭니다.

해결책을 찾기 위한 접근 방식

이 접근 방식에서 우리는 지금 후위 순회(post-order traversal)로 순회합니다. 경로 길이가 k보다 작은 리프 노드를 재귀적으로 제거하고 다음과 같이 계속합니다.

예시

위 접근 방식에 대한 C++ 코드

#include<bits/stdc++.h>
using namespace std;
struct Node{ // structure of our node
    char data;
    Node *left, *right;
};
Node *newNode(int data){ // inserting new node
    Node *node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
Node *trimmer(Node *root, int len, int k){
    if (!root) // if root == NULL then we return
        return NULL;
    root -> left = trimmer(root -> left, len + 1, k); // traversing the left phase
    root -> right = trimmer(root -> right, len + 1, k); // traversing the right phase
    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;
}

출력

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

위 코드 설명

이 코드에서 우리는 트리를 순회하고 왼쪽 및 오른쪽 하위 트리의 통계를 유지하는 재귀 함수를 사용하고 있습니다. 이제 리프 노드에 도달합니다. 해당 노드까지의 경로 길이를 확인합니다. 경로 길이가 더 짧으면 이 노드를 삭제하고 NULL을 반환합니다. 그렇지 않으면 코드가 계속됩니다.

결론

이 자습서에서는 재귀를 사용하여 길이