資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中二叉樹的最大螺旋和
在這個問題中，我們給定一個二叉樹。我們的任務是建立一個程式，該程式將在 C++ 中找到二叉樹中的最大螺旋和。
螺旋和二叉樹是指在二叉樹的螺旋遍歷中遇到的節點的總和。
在樹的螺旋遍歷中，節點從根節點遍歷到葉節點。遍歷從左到右進行，然後對於下一層從右到左進行，依此類推，對於更深層級也是如此。
示例 -
輸出 -5
說明 -
我們將考慮螺旋遍歷，直到樹的第 2 層的第一個節點。
1+ 5 = 5.
第三行的元素和 (1-9+6-4 = -6) 會降低總和，因此在考慮最大和時將其排除。
為了解決這個問題，我們將使用一個數組來儲存每層元素的和，並且為了找到每層的螺旋和，我們將使用兩個棧。然後在最後，我們將檢查包含該層之後的和是否會增加最大和，如果是，那麼我們將保留它，否則丟棄其餘的螺旋。
示例
查詢二叉樹中最大螺旋和的程式
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
Node* insertNode(int data){
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
int findMaxSum(vector<int> arr, int n){
int sum = INT_MIN;
int maxSum = INT_MIN;
for (int i = 0; i < n; i++) {
if (sum < 0)
sum = arr[i];
else
sum += arr[i];
maxSum = max(maxSum, sum);
}
return maxSum;
}
int SpiralSum(Node* root){
if (root == NULL)
return 0;
stack<Node*> sRtL;
stack<Node*> sLtR;
vector<int> arr;
sRtL.push(root);
while (!sRtL.empty() || !sLtR.empty()) {
while (!sRtL.empty()) {
Node* temp = sRtL.top();
sRtL.pop();
arr.push_back(temp->data);
if (temp->right)
sLtR.push(temp->right);
if (temp->left)
sLtR.push(temp->left);
}
while (!sLtR.empty()) {
Node* temp = sLtR.top();
sLtR.pop();
arr.push_back(temp->data);
if (temp->left)
sRtL.push(temp->left);
if (temp->right)
sRtL.push(temp->right);
}
}
return findMaxSum(arr, arr.size());
}
int main(){
Node* root = insertNode(1);
root->left = insertNode(5);
root->right = insertNode(-1);
root->left->left = insertNode(-4);
root->left->right = insertNode(6);
root->right->left = insertNode(-9);
root->right->right = insertNode(1);
cout << "Maximum Spiral Sum in binary tree : "<<SpiralSum(root);
return 0;
}輸出
Maximum Spiral Sum in binary tree : 6
更新於: 2020年6月3日
97 次瀏覽
廣告