完全二叉树遍历，并求解分支最大和

#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();                                     //左右子树访问完成后根节点的和出栈
    if (!sums.empty())
    {
        sum = sums.top();                           //上一个结点的和
    }
}
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个结点，且每一个结点初始化为0

    for (int i = 1; i <= n; i++)
    {
        cin >> tree[p[i]];          //构造完全二叉树
    }

    PreTraverse(tree, 1, maxNode);
    cout << MaxValue << endl;

    return 0;
}