資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中給定二叉樹所有層級的非葉子節點的最大和
在這個問題中，我們給定一棵二叉樹。我們的任務是建立一個程式，在C++中找到給定二叉樹所有層級中非葉子節點的最大和。
問題描述 - 我們將計算樹中每一層所有非葉子節點的和，然後列印最大和。
讓我們來看一個例子來理解這個問題：
輸入 -
輸出 - 9
解釋 - 每層非葉子節點的和：
Level 1: 4 Level 2: 1+2 = 3 Level 3: 9 (4, 7 are leaf nodes) Level 4: 0
為了解決這個問題，我們必須進行二叉樹的層序遍歷，找到所有非葉子節點的和，然後找到它們的 最大和。
因此，在每一層，我們將檢查節點是否具有左子節點或右子節點，如果沒有，則將其新增到總和中。 並維護一個maxSum變數，它儲存到該層為止的最大和。如果所有非葉子節點的和大於maxSum，那麼我們將把該層的和初始化為最大值。
示例
程式演示了我們解決方案的實現：
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
int maxLevelSum(struct Node* root){
if (root == NULL)
return 0;
int maxSum = root->data;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int count = q.size();
int levelSum = 0;
while (count--) {
Node* temp = q.front();
q.pop();
if (temp->left != NULL || temp->right != NULL)
levelSum = levelSum + temp->data;
if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);
}
maxSum = max(levelSum, maxSum);
}
return maxSum;
}
struct Node* insertNode(int data) {
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int main() {
struct Node* root = insertNode(6);
root->left = insertNode(1);
root->right = insertNode(2);
root->left->left = insertNode(4);
root->left->right = insertNode(7);
root->right->right = insertNode(9);
root->right->right->left = insertNode(5);
cout<<"The maximum sum of all non-lead nodes at a level of the binary tree is "<<maxLevelSum(root);
return 0;
}輸出
The maximum sum of all non-lead nodes at a level of the binary tree is 9
更新於：2020年6月3日
129 次瀏覽
廣告