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

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * dfs：
     * 最关键的就是用currentPath计算当前节点的val+left+right是多少
     * 通过return把子结点的path传给了父结点
     */

    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum (TreeNode root) {
        dfs(root);
        return maxSum;
    }

    public int dfs(TreeNode root) {
        if (root == null) return 0;

        //负数就不要
        int left = Math.max(0, dfs(root.left));
        int right = Math.max(0, dfs(root.right));

        //计算以当前节点为拐点的最大路径值(左+中+右)
        //用它去尝试更新全局最高纪录
        int currentPath = root.val + left + right;
        maxSum = Math.max(maxSum, currentPath);

        //把当前节点的最大路径值返回给父结点,注意此时只能返回左或右边的其中一条路
        return root.val + Math.max(left, right);
    }
}