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

LeetCode 题解：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-leetcode-/

import java.io.*;
import java.util.*;

/**
 * LeetCode: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
 */
public class Main {
    static int maxSum = Integer.MIN_VALUE;
    static int n;
    static int[] val, parent;
    static int[][] child;
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter pw = new PrintWriter(System.out);
        
        st.nextToken();
        n = (int) st.nval;
        val = new int[n];
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            st.nextToken();
            val[i] = (int) st.nval;
        }
        for (int i = 0; i < n; i++) {
            st.nextToken();
            parent[i] = (int) st.nval;
        }
        
        child = new int[n][2];
        for (int i = 0; i < n; i++) {
            child[i][0] = child[i][1] = -1;
            if (parent[i] > 0) {
                int[] childNode = child[parent[i] - 1];
                if (childNode[0] == -1) {
                    childNode[0] = i;
                } else {
                    childNode[1] = i;
                }
            }
        }
        
        maxGain(0);
        pw.println(maxSum);
        
        pw.flush();
        pw.close();
    }
    
    /**
     * 计算二叉树中的一个节点的最大贡献值
     * <p>
     * 在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大
     * <p>
     * 1. 空节点的最大贡献值等于 0
     * <p>
     * 2. 非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）。
     */
    private static int maxGain(int index) {
        if (index == -1) {
            return 0;
        }
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(child[index][0]), 0);
        int rightGain = Math.max(maxGain(child[index][1]), 0);
        
        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = val[index] + leftGain + rightGain;
        // 更新答案
        maxSum = Math.max(maxSum, priceNewpath);
        // 返回节点的最大贡献值
        return val[index] + Math.max(leftGain, rightGain);
    }
}