C++ を使用して、どのパス上にも存在せず、パスの合計が k 未満であるすべてのノードを削除します。

この問題には、ルート ノードからリーフ ノードまでのパスが完全に定義されているバイナリ ツリーがあります。ルート ノードからリーフ ノードまでのすべてのノードの合計は k 以上である必要があります。したがって、合計が k 未満であるパス内のすべてのノードを削除する必要があります。ここで覚えておくべき重要なことは、ノードは多くのパスの一部である可能性があるため、そのようなノードはすべてのパスの合計が k 未満の場合にのみ削除されるということです。

ルート ノードからリーフ ノードまでの合計を計算できます。ノードへの再帰呼び出しが完了して制御が戻ると、左右のパスの合計が k

150 K と次のようなツリーがあるとします。 -

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

パス root->left->left の合計が 10 20 5 で、これは 25 であることがわかります。は 150 未満です。プルーニングして 5 を削除する必要があります。その後、10→30→40と評価してみましょう。 150未満なので40を削除します。ここで、別のパス 10->20->35->50 が表示されます。115 の合計は 150 未満なので、50 を削除します。

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

すべてのパスの合計が 150 を超えるパスが残っているため、これ以上プルーニングする必要はありません。

例

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

出力

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

完全に剪定された木 -

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

結論

ご覧のとおり、最初の観察後、再帰関数が各呼び出しから返されるときにそのノードの合計を計算することで、DFS を適用してノードを削除できます。全体として、これは観察と方法論に関する単純な問題です。

以上がC++ を使用して、どのパス上にも存在せず、パスの合計が k 未満であるすべてのノードを削除します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。