在這個問題中,我們有一個二元樹,其從根節點到葉節點的路徑是完全定義的。從根節點到葉子節點的所有節點總和必須大於或等於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,因此我們不需要再修剪。
#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 並在遞歸函數從每次呼叫返回時透過計算該節點的總和來刪除節點。總的來說,這是一個簡單的觀察和方法論問題。
以上是使用C++實作刪除所有不在任何路徑上且路徑和小於k的節點的詳細內容。更多資訊請關注PHP中文網其他相關文章!