C++程序：移除路径总和>=k的路径上不存在的节点

在这个问题中，我们有一棵二叉树，其中从根节点到叶子节点的路径是完全定义的。从根节点到叶子节点的所有节点的总和必须大于或等于一个常数k。因此，我们需要移除所有路径总和小于k的路径中的节点，以便树中仅保留总和大于k的路径。这里需要注意的是，一个节点可能属于多个路径，因此只有当所有通向该节点的路径的总和小于k时，才需要移除该节点。

从根节点到叶子节点，我们可以计算总和。当递归调用对于某个节点完成并返回控制权时，我们可以检查左右路径的总和是否小于k。如果左右路径的总和都小于k，则需要移除此节点。

假设我们有k=150，并且有一棵这样的树：

                  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，因此我们不再需要进行剪枝。

示例

以下是一个C++程序，演示了如何移除所有路径总和不满足大于或等于任意常数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;
}

输出

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

结论

我们可以看到，在初步观察后，我们可以应用深度优先搜索，并在递归函数从每个调用返回时通过计算该节点处的总和来移除节点。总的来说，这是一个简单的观察和方法论问题。

更新于： 2022年8月10日

128 次浏览

开启你的职业生涯

通过完成课程获得认证

立即开始
广告