在这个问题中，我们有一个二叉树，其从根节点到叶节点的路径是完全定义的。从根节点到叶节点的所有节点的总和必须大于或等于常数值 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。
立即学习“C++免费学习笔记（深入）”；
现在我们看到另一条路径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 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 left); cout value 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: 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的节点的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2581797.html
