Gunakan C++ untuk memadam semua nod yang tidak berada di mana-mana laluan dan jumlah laluan adalah kurang daripada k

Dalam masalah ini, kami mempunyai pokok binari yang laluannya dari nod akar ke nod daun ditakrifkan sepenuhnya. Jumlah semua nod dari nod akar ke nod daun mestilah lebih besar daripada atau sama dengan k. Jadi kita perlu memadam semua nod dalam laluan yang jumlahnya kurang daripada k. Perkara penting yang perlu diingat di sini ialah nod mungkin sebahagian daripada banyak laluan, jadi nod tersebut hanya dialih keluar jika jumlah semua laluan

Dari nod akar ke nod daun, kita boleh mengira jumlahnya. Apabila panggilan rekursif ke nod selesai dan kawalan kembali, kita boleh menyemak sama ada jumlah laluan kiri dan kanan

Katakan kita mempunyai 150 K dan pokok seperti ini -

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

Jika kita lihat jumlah akar laluan->kiri->kiri ialah 10 + 20 + 5 iaitu 25 iaitu kurang daripada 150 kita perlu memangkasnya dan memadam 5. Selepas itu, mari kita nilai 10->30->40. Ia kurang daripada 150, jadi padamkan 40. Sekarang kita melihat laluan lain 10->20->35->50, jumlah 115 adalah kurang daripada 150, jadi kita padamkan 50. Sekarang laluan kami yang tinggal ialah

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

Jumlah semua laluan lebih besar daripada 150, jadi kami tidak perlu memangkas lagi.

Contoh

#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;
}

Output

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

Pokok kami yang dipangkas sepenuhnya -

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

Kesimpulan

Seperti yang dapat kita lihat, selepas pemerhatian awal, kita boleh menggunakan DFS dan lulus fungsi rekursif semasa ia mengembalikan jumlah panggilan daripada setiap nod ini untuk mengeluarkan nod. Secara keseluruhannya, ini adalah pemerhatian dan metodologi yang mudah.

Atas ialah kandungan terperinci Gunakan C++ untuk memadam semua nod yang tidak berada di mana-mana laluan dan jumlah laluan adalah kurang daripada k. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!