数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学使用C++移除所有不在任何路径和>=k的节点
在这个问题中，我们有一棵二叉树，其根节点到叶子节点的路径完全定义。从根节点到叶子节点的所有节点的总和必须大于或等于k。因此，我们需要移除所有路径和少于k的节点。这里需要注意的是，一个节点可能属于许多路径，因此只有在所有路径的和都小于k时才移除该节点。
从根节点到叶子节点，我们可以计算路径和。当节点的递归调用完成并返回控制权时，我们可以检查左右两条路径的和是否小于k。如果左右两条路径的和都小于k，则需要移除此节点。
假设我们有k=150和如下所示的树：
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)，并在递归函数从每个调用返回时通过计算该节点的和来移除节点。总的来说，这是一个简单的观察性和方法性问题。
更新于：2022年5月18日
163 次浏览
广告