二叉树中的最大路径和

#include<bits/stdc++.h>
using namespace std;

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode():val(0),left(nullptr),right(nullptr){}
    TreeNode(int _val):val(_val),left(nullptr),right(nullptr){}
    TreeNode(int _val, TreeNode* _left, TreeNode* _right) : val(_val), left(_left), right(_right) {}
};

vector<TreeNode*> myMap;
void buildTree(vector<int>& values, vector<int>& fathers){
    int n = values.size();
    if(n == 0) return;
    for(auto val : values){
        myMap.push_back(new TreeNode(val));
    }
    for(int i = 1; i < n; i++){
        if(!myMap[fathers[i] - 1]->left){
            myMap[fathers[i] - 1]->left = myMap[i];
        }
        else{
            myMap[fathers[i] - 1]->right = myMap[i];
        }
    }
}

class Solution {
public:
    int ans;
    int maxPathSum(TreeNode* root) {
        ans = INT_MIN;
        dfs(root);
        return ans;
    }

    int dfs(TreeNode* root){
        if(root == nullptr) return 0;//遇到空节点返回0
        int leftValue = dfs(root->left);
        int rightValue = dfs(root->right);
        //更新最大路径和(注意4种更新方式)
        if(leftValue >= 0 && rightValue <= 0){//情况1
            ans = max(ans, leftValue + root->val);
            return leftValue + root->val;
        }
        if(leftValue <= 0 && rightValue >= 0){//情况2
            ans = max(ans, rightValue + root->val);
            return rightValue + root->val;
        }
        if(leftValue >= 0 && rightValue >= 0){//情况3
            ans = max(ans, leftValue + rightValue + root->val);
            return max(leftValue, rightValue) + root->val;
        }
        ans = max(ans,root->val);//情况4
        return root->val;
    }
};


int main(){
    int n;
    while(cin >> n){
        vector<int> values(n);
        vector<int> fathers(n);
        for(int i = 0; i < n; i++){
            cin >> values[i];
        }
        for(int i = 0; i < n; i++){
            cin >> fathers[i];
        }
        buildTree(values, fathers);
        Solution s;
        cout << s.maxPathSum(myMap[0]) << endl; 
        myMap.clear();
    }
}

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, INF = 0x3fffffff;
int v[N], ne[N], h[N], a[N], w[N];
int idx, ans;

void add(int a, int b){
    v[idx]=b, ne[idx]=h[a], h[a]=idx++;
}

int dfs(int u){
    int d1 = 0, d2 = 0;//d1,d2分别代表以u为根节点的所有子树的最大与次大路径和，路径为负就不选，初始化为0
    for(int i=h[u]; i!=-1; i=ne[i]){
        int j=v[i];
        int d = dfs(j)+w[j];
        if(d >= d1) d2 = d1, d1 = d;
        else if(d > d2) d2 = d;
    }
    ans = max(ans, d1+d2+w[u]);
    return d1;
}

int main() {
    memset(h, -1, sizeof h);
    idx = 0, ans = -INF;
    int n;
    cin >> n;
    for(int i=1; i<=n; i++)cin >> w[i];
    for(int i=1; i<=n; i++){
        int id;
        cin >> id;
        add(id, i);
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int _v):val(_v),left(nullptr),right(nullptr){}
};
int res = INT_MIN;
int fun(Node* root){
    if(!root) return 0;
    int left = max(fun(root -> left),0);
    int right = max(fun(root -> right),0);
    res = max(res,left + right + root -> val);
    return max(root -> val + left,root -> val + right);
    
}
int main(){
    int n ;
    cin >> n;
    int value;
    vector<Node*> node;
    for( int i = 0; i < n; i++){
        
        cin >> value;
        auto temp = new Node(value);
        node.push_back(temp);
    }
    Node* root;
    for( int i = 0; i < n; i++){
        cin >> value;
        if(value == 0){
            root = node[i];
            continue;
        }
        if(! node[value - 1] -> left){
            node[value - 1] -> left = node[i];
        }else{
            node[value - 1] -> right = node[i];
        }
    }
    fun(root);
    cout<<  res;
    return 0;
    
}

import java.util.*; 

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static class Node {
        public Node(int val) {
            this.val = val;
        }
        public int val;
        public Node left;
        public Node right;
    }
    public static int ans = Integer.MIN_VALUE;
    public static Map<Integer, Node> map = new HashMap<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int nodeNum = in.nextInt();
        in.nextLine();
        if (nodeNum == 0) {
            return;
        }
        int[][] child = new int[nodeNum][2];
        String[] strings1 = in.nextLine().split(" ");
        String[] strings2 = in.nextLine().split(" ");
        for (int i = 1; i <= nodeNum; i++) {
            map.put(i, new Node(Integer.valueOf(strings1[i-1])));
            if (map.get(Integer.valueOf(strings2[i-1])) != null) {
                if (map.get(Integer.valueOf(strings2[i-1])).left == null) {
                    map.get(Integer.valueOf(strings2[i-1])).left = map.get(i);
                } else {
                    map.get(Integer.valueOf(strings2[i-1])).right = map.get(i);
                }
            }
        }

        
        Node root = map.get(1);
        dfs(root);
        System.out.println(ans);
    }

    public static int dfs(Node root) {
        if (root == null) {
            return 0;
        }
        int maxL = Math.max(dfs(root.left), 0);
        int maxR = Math.max(dfs(root.right), 0);

        ans = Math.max(ans, root.val + maxL + maxR);
        return Math.max(root.val + maxL, root.val + maxR);
    }
}

import java.util.*;
public class Main {
    static int maxSum = Integer.MIN_VALUE;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] nodeVal = new int[n];
        for (int i = 0; i < n; i++) {
            nodeVal[i] = scan.nextInt();
        }
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = scan.nextInt();
        }
        TreeNode root = buildTree(nodeVal, parent);
        maxPathSum(root);
        System.out.println(maxSum);
    }
    
    public static TreeNode buildTree(int[] nodeVal, int[] parent) {
        TreeNode[] nodes = new TreeNode[nodeVal.length];
        for (int i = 0; i < nodeVal.length; i++) {
            TreeNode node = new TreeNode(nodeVal[i]);
            nodes[i] = node;
        }
        TreeNode root = nodes[0];
        for (int i = 1; i < parent.length; i++) {
            TreeNode curNode = nodes[i];
            TreeNode parentNode = nodes[parent[i] - 1];
            if (parentNode.left == null) {
                parentNode.left = curNode;
            } else {
                parentNode.right = curNode;
            }
        }
        return root;
    }
    
    public static int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftGain = Math.max(maxPathSum(root.left), 0);
        int rightGain = Math.max(maxPathSum(root.right), 0);
        int priceNewpath = root.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, priceNewpath);
        return root.val + Math.max(leftGain, rightGain);
    }
    
    static class TreeNode {
        TreeNode left;
        TreeNode right;
        int val;
        public TreeNode(int val) {
            this.val = val;
        }
    }
}

leecode 124题，可以100%通过，牛客网不行，有点奇怪哦；
我觉得难点在于构造二叉树吧，leecode是核心代码模式，acm要自己构造二叉树，挺难受的。

while(line = readline()){
    var n = parseInt(line);
    var node = readline().split(' ').map(Number);
    var fa = readline().split(' ').map(Number);
    deal(n,node,fa);

}
function deal(n,node,f){
    var root = construct_bst(n,node,f);
     var res = -1000;
    maxDepth(root);
    console.log(res)
    function maxDepth(root){
        if(root == null) {
            return 0;
        }
        var left = maxDepth(root.left);
        var right = maxDepth(root.right);
        res = Math.max(res, left+right+root.val);
        // 返回当前子树的路径和 分为走左边、右边、不动 3种情况
        var sum = root.val+Math.max(0,left,right);
        return sum < 0 ? 0 : sum;
    }
}
function TreeNode(val){
    this.val = val;
    this.left = null;
    this.right = null;
}
function construct_bst(n,node,fa){
   var Node = [];
    for(var i = 0; i < n; i++){
        var temp = new TreeNode(node[i]);
        Node.push(temp);
    }
    var root = Node[0];
    for(var i = 1; i < n; i++){
        if(!Node[fa[i]].left) {
            Node[fa[i]-1].left = Node[i]
        } else{
            Node[fa[i]-1].right = Node[i]
        }
    }
    return root;
}