在这个问题中,我们有一个二叉树,其从根节点到叶节点的路径是完全定义的。从根节点到叶节点的所有节点的总和必须大于或等于常数值 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。
现在我们看到另一条路径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
结论
正如我们所看到的,在初始观察之后,我们可以应用 DFS 并在递归函数从每次调用返回时通过计算该节点的总和来删除节点。总的来说,这是一个简单的观察和方法论问题。