题解 | #二叉树中的最大路径和#

#include <bits/stdc++.h>

using namespace std;


//构建树结构
struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int _val):val(_val),left(nullptr),right(nullptr) {}
};

int maxRes;    //全局变量，用来记录最大结果


//计算每个节点的贡献值，采用递归的方式，深度优先逐个节点进行计算，找出最大值
int traverse(TreeNode* root)
{
    if(root == nullptr)
        return 0;
    int Left_val = max(traverse(root->left),0);
    int Right_val = max(traverse(root->right),0);
    
    
    int sum = root->val + Left_val + Right_val;
    maxRes = max(maxRes,sum);
    
    return root->val + max(Left_val,Right_val);
}



int main()
{
    int n;
    while(cin>>n)
    {
        maxRes = INT_MIN;
        vector<TreeNode *> trees;
      
        for(int i = 0;i<n;++i)
        {
            int val;
            cin>>val;
            trees.emplace_back(new TreeNode(val));
            
        }
        //用来找到哪个节点是根节点
        int root;
        
        //根据相关关系来构造树的关系并且找到树的根节点
        for(int i = 0;i<n;++i)
        {
            int father;
            cin>>father;
            
            if(father == 0)
            {
                root = i;
            }
            else
            {
                if(trees[father-1]->left == nullptr)
                {
                    trees[father-1]->left = trees[i];
                }
                else
                {
                    trees[father-1]->right = trees[i];
                }
            }
        }
        TreeNode * root_tree = trees[root];
        traverse(root_tree);
        cout<<maxRes<<endl;   
    }
    
    
    
}