Utilisez C++ pour supprimer tous les nœuds qui ne se trouvent sur aucun chemin et dont la somme du chemin est inférieure à 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 à k. Nous devons donc supprimer tous les nœuds du chemin dont la somme est inférieure à 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

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 la somme du chemin racine->gauche->gauche est 10 + 20 + 5, soit 25, soit moins de 150, nous avons besoin pour l'élaguer et supprimer 5. Après cela, évaluons 10->30->40. C'est moins de 150, alors supprimez 40. Maintenant, nous voyons un autre chemin 10->20->35->50, la somme de 115 est inférieure à 150, donc nous supprimons 50. Maintenant, nos chemins restants sont

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

#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 élagué -

         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 transmettre la fonction récursive à son retour de chaque appel Calculer la somme de ce nœud pour supprimer le nœud. 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!