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

#include <bits/stdc++.h>
using namespace std;
int ans=INT_MIN;
int dfs(vector<vector<int>>& val,int i){
    if(i==0){
        return 0;
    }
    int left=max(dfs(val,val[1][i]),0);
    int right=max(dfs(val,val[2][i]),0);
    int sum=left+right+val[0][i];
    ans=max(ans,sum);
    return max(left,right)+val[0][i];
}

int main() {
    int n;
    cin>>n;
    vector<vector<int>> val(3,vector<int>(n+1,0));
    for(int i=1;i<=n;i++){
        cin>>val[0][i];
    }
    for(int i=1;i<=n;i++){
        int temp;
        cin>>temp;
        if(val[1][temp]==0){
            val[1][temp]=i;
        }else{
            val[2][temp]=i;
        }
    }
    
    dfs(val,1);
    cout<<ans<<endl;
    return 0;

}
// 64 位输出请用 printf("%lld")

把存储方式变成 父->子 之后，和leetcode LCR051一模一样，我只会用这种方式遍历二叉树。