C ++は、長さがK未満のルートからリーフへのパス上のノードを削除します

たとえば、ツリーが与えられ、与えられた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未満の場合にリーフノードを削除する再帰関数を作成します。

解決策を見つけるためのアプローチ

このアプローチでは、現在、ポストオーダートラバーサルでトラバースします。パス長が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を返します。それ以外の場合、コードは続行されます。

結論

このチュートリアルでは、再帰を使用して、ルートからリーフへの長さ