C++를 사용하여 어떤 경로에도 없고 경로 합이 k보다 작은 모든 노드를 삭제합니다.

이 문제에는 루트 노드에서 리프 노드까지의 경로가 완전히 정의된 이진 트리가 있습니다. 루트 노드부터 리프 노드까지 모든 노드의 합은 k보다 크거나 같아야 합니다. 따라서 합이 k보다 작은 경로의 모든 노드를 삭제해야 합니다. 여기서 기억해야 할 중요한 점은 노드가 여러 경로의 일부일 수 있으므로 이러한 노드는 모든 경로의 합

루트 노드부터 리프 노드까지 합을 계산할 수 있습니다. 노드에 대한 재귀 호출이 완료되고 제어가 반환되면 왼쪽 및 오른쪽 경로의 합이

150K와 이와 같은 트리가 있다고 가정합니다 -

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

루트->왼쪽->왼쪽 경로의 합이 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보다 크므로 더 이상 정리할 필요가 없습니다.

Example

#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

완전히 가지치기된 트리 -

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

Conclusion

보다시피, 초기 관찰 후 DFS를 적용하고 각 호출에서 반환될 때 재귀 함수를 전달할 수 있습니다. 이 노드를 사용하여 노드를 제거합니다. 전반적으로 이것은 관찰과 방법론의 단순한 문제입니다.

위 내용은 C++를 사용하여 어떤 경로에도 없고 경로 합이 k보다 작은 모든 노드를 삭제합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!