数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学用 C++ 查找二叉树中最大层积
假设有一个二叉树。它既有正节点，又有负节点。我们需要找出其每一层的最大乘积。
考虑这是这颗树，因此第 0 层的积是 4，第 1 层的积是 2 * -5 = -10，第 2 层的积是 -1 * 3 * -2 * 6 = 36。因此，这是最大值。
为了解决此问题，我们将执行树的层次遍历，在遍历期间，对不同层的节点进行单独处理。然后获得最大乘积。
示例
#include<iostream>
#include<queue>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
};
Node* getNode(int data) {
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
int getMaxLevelProduct(Node* root) {
if (root == NULL)
return 0;
int res = root->data;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int count = q.size();
int prod = 1;
while (count--) {
Node* temp = q.front();
q.pop();
prod *= temp->data;
if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);
}
res = max(prod, res);
}
return res;
}
int main() {
Node* root = getNode(4);
root->left = getNode(2);
root->right = getNode(-5);
root->left->left = getNode(-1);
root->left->right = getNode(3);
root->right->left = getNode(-2);
root->right->right = getNode(6);
cout << "Maximum level product is " << getMaxLevelProduct(root) << endl;
}输出
Maximum level product is 36
更新于：2019 年 12 月 19 日
94 次浏览
广告