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