数据结构
网络
关系数据库管理系统(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 次浏览
广告