#include <iostream>
#include <map>
#include <vector>
#include <stack>
using namespace std;
//遍歷二叉樹每個分支求最大值
int sum = 0;
int MaxValue = 0;
/*
4
2 3 4 5
2 5 2 4
*/
stack<int> sums;
//完全二叉樹的前序遍歷并求解分支最大和路徑
void PreTraverse(vector<int> tree, int index, int n)
{
if (index > n) //該分支如果訪問完成
{
if (sum > MaxValue) //分支的和是否為最大
{
MaxValue = sum; //更新最大分支和
}
return;
}
//cout << tree[index] << " ";
sum += tree[index]; //計算每個分支的和
sums.push(sum); //分支和入棧
PreTraverse(tree, 2 * index, n); //左子樹
PreTraverse(tree, 2 * index + 1, n); //右子樹
sums.pop(); //左右子樹訪問完成后根節(jié)點的和出棧
if (!sums.empty())
{
sum = sums.top(); //上一個結(jié)點的和
}
}
int main(int argc, char** argv)
{
int n;
cin >> n;
int maxNode = 0;
vector<int> p;
vector<int> tree; //初始化一個完全二叉樹
p.resize(n + 1); //p
for (int i = 1; i <= n; i++)
{
cin >> p[i];
if (p[i] > maxNode)
{
maxNode = p[i];
}
}
tree.resize(maxNode + 1); //最多有maxNode個結(jié)點听想，且每一個結(jié)點初始化為0
for (int i = 1; i <= n; i++)
{
cin >> tree[p[i]]; //構(gòu)造完全二叉樹
}
PreTraverse(tree, 1, maxNode);
cout << MaxValue << endl;
return 0;
}
完全二叉樹遍歷奸鸯，并求解分支最大和
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來剃浇，“玉大人巾兆，你說我怎么就攤上這事』⑶簦” “怎么了角塑？”我有些...
- 文/不壞的土叔 我叫張陵，是天一觀的道長淘讥。 經(jīng)常有香客問我圃伶，道長，這世上最難降的妖魔是什么蒲列？ 我笑而不...
- 正文 為了忘掉前任窒朋，我火速辦了婚禮，結(jié)果婚禮上蝗岖，老公的妹妹穿的比我還像新娘侥猩。我一直安慰自己，他們只是感情好抵赢，可當我...
- 文/花漫 我一把揭開白布欺劳。 她就那樣靜靜地躺著唧取，像睡著了一般。 火紅的嫁衣襯著肌膚如雪划提。 梳的紋絲不亂的頭發(fā)上枫弟，一...
- 文/蒼蘭香墨 我猛地睜開眼湾碎，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了奠货？” 一聲冷哼從身側(cè)響起介褥，我...
- 正文 年R本政府宣布光酣，位于F島的核電站疏遏，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏救军。R本人自食惡果不足惜财异，卻給世界環(huán)境...
- 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望唱遭。 院中可真熱鬧戳寸，春花似錦、人聲如沸拷泽。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至订晌，卻和暖如春虏辫，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背锈拨。 一陣腳步聲響...
推薦閱讀更多精彩內(nèi)容
- 樹 在計算機科學中兔院，樹（英語：tree）是一種抽象數(shù)據(jù)類型或是實現(xiàn)這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)...
- 完全二叉樹舉例： 一站削、廣度優(yōu)先遍歷：對每一層節(jié)點依次訪問坊萝，訪問完一層進入下一層，而且每個節(jié)點只能訪問一次许起。對于例子...
- 1、概念 搜索二叉樹(Binary Search Tree - BST) 它的左子樹不空猛频，則左子樹上所有結(jié)點的值均...
- 1.首先我們了解什么是完全二叉樹 完全二叉樹: 葉子節(jié)點只會出現(xiàn)最后2層狮崩，且最后1層的葉子節(jié)點都靠左對齊蛛勉。 2.這...
