从根节点到叶节点，我们可以计算总和。当节点的递归调用完成并且控制返回时，我们可以检查左路径和右路径的总和是否
假设我们有 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 65inorder 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的节点的详细内容。