資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告