Programme C++ pour supprimer les nœuds qui ne satisfont pas le chemin et qui sont supérieurs ou égaux à k

Dans ce problème, nous avons un arbre binaire dont le chemin du nœud racine au nœud feuille est entièrement défini. La somme de tous les nœuds du nœud racine aux nœuds feuilles doit être supérieure ou égale à la valeur constante k. Par conséquent, nous devons supprimer tous les nœuds des chemins dont la somme est inférieure à k, de sorte que les chemins restants dans l’arborescence soient supérieurs à k. La chose importante à retenir ici est qu'un nœud peut faire partie de plusieurs chemins, donc ces nœuds ne sont supprimés que si la somme de tous les chemins menant à ce nœud

Du nœud racine aux nœuds feuilles, nous pouvons calculer la somme. Lorsque l'appel récursif au nœud est terminé et que le contrôle revient, nous pouvons vérifier si la somme des chemins gauche et droit

Supposons que nous ayons 150 K et un arbre comme celui-ci -

                  10
                  /\
                 20 30
                /\   /\
              5  35 40 45
                 /\     /\
               50  55 60  65
                   /\  /  /
                 70 80 90 100

Si nous voyons que la somme du chemin racine->gauche->gauche est 10 + 20 + 5, soit 25, inférieur à 150, nous devons l'élaguer et supprimer 5. Après cela, évaluons 10->30->40. Il est inférieur à 150, donc 40 est supprimé.

Maintenant, nous voyons un autre chemin 10->20->35->50, la somme de 115 est inférieure à 150, donc nous supprimons 50. Maintenant, notre chemin restant est

10->20->35->55->70 ;
10->20->35->55->80 ;
10->30->45->60->90 ;
10->30->45->65->100 ;

La somme de tous les chemins est supérieure à 150, nous n’avons donc plus besoin de tailler.

Exemple

Voici un programme C++ qui montre comment supprimer des nœuds qui ne se trouvent dans aucun chemin et dont la somme est supérieure ou égale à n'importe quelle valeur constante k -

#include <iostream>
using namespace std;
class Node {
   public:
   int value;
   Node *left, *right;
   Node(int value) {
      this->value = value;
      left = right = NULL;
   }
};
Node* removeNodesWithPathSumLessThanK(Node* root, int k, int& sum) {
   if(root == NULL) return NULL;
   int leftSum, rightSum;
   leftSum = rightSum = sum + root->value;
   root->left = removeNodesWithPathSumLessThanK(root->left, k, leftSum);
   root->right = removeNodesWithPathSumLessThanK(root->right, k, rightSum);
   sum = max(leftSum, rightSum);
   if(sum < k) {
      free(root);
      root = NULL;
   }
   return root;
}
void printInorderTree(Node* root) {
   if(root) {
      printInorderTree(root->left);
      cout << root->value << " ";
      printInorderTree(root->right);
   }
}
int main() {
   int k = 150;
   Node* root = new Node(10);
   root->left = new Node(20);
   root->right = new Node(30);
   root->left->left = new Node(5);
   root->left->right = new Node(35);
   root->right->left = new Node(40);
   root->right->right = new Node(45);
   root->left->right->left = new Node(50);
   root->left->right->right = new Node(55);
   root->right->right->left = new Node(60);
   root->right->right->right = new Node(65);
   root->left->right->right->left = new Node(70);
   root->left->right->right->right = new Node(80);
   root->right->right->left->left = new Node(90);
   root->right->right->right->left = new Node(100);
   int sum = 0;
   cout << "Inorder tree before: ";
   printInorderTree(root);
   root = removeNodesWithPathSumLessThanK(root, k, sum);
   cout << "\nInorder tree after: ";
   printInorderTree(root);
   return 0;
}

Sortie

Inorder tree before: 5 20 50 35 70 55 80 10 40 30 90 60 45 100 65 
Inorder tree after: 20 35 70 55 80 10 30 90 60 45 100 65 

Notre arbre entièrement taillé -

                  10
                  / \
                 20  30
                 \     \
                 35     45
                  \     /\
                  55   60 65
                  /\    /  /
                 70 80 90 100

Conclusion

Comme nous pouvons le voir, après l'observation initiale, nous pouvons appliquer DFS et supprimer des nœuds en calculant la somme de ce nœud au fur et à mesure que la fonction récursive revient de chaque appel. Dans l’ensemble, c’est une simple question d’observation et de méthodologie.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!