LeetCode124: 二叉树中的最大路径和

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]

   1
  / \
 2   3

输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]

输出: 42

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum

解题思路：

• 首先想到用递归实现DFS遍历所有的点
• 更新当前节点，节点值表示此节点为根节点的子树如果被上级路径连接，它能贡献的最大路径和 ：
  rootValue = Math.max(rootValue, rootValue+leftValue, rootValue+rightValue);
  这里不能加rootValue+leftValue+rightValue是因为路径不能走回头路！！！
  -更新结果：
  result = Math.max(leftValue, rightValue, result, rootValue, leftValue + rightValue + rootValue);

public class MaxPathSum {
    static int result = -0x3f3f3f3f;

    public int maxPathSum(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return root.val;
        result = -0x3f3f3f3f;
        dfs(root);
        return result;
    }

    private int dfs(TreeNode root) {
        if (root.left == null && root.right == null) return root.val;
        int leftValue = 0;
        int rightValue = 0;
        if (root.left != null) {
            leftValue = dfs(root.left);
            result = Math.max(leftValue, result);
        }
        if (root.right != null) {
            rightValue = dfs(root.right);
            result = Math.max(rightValue, result);
        }
        //定义sum是因为路径不能重复，因此如果当前点要是想和上一级点连接，就只能取leftValue + root.val 或者rightValue + root.val或者root.val
        int sum = rightValue + root.val + leftValue;
        root.val = Math.max(Math.max(rightValue + root.val, root.val), leftValue + root.val);
        result = Math.max(result,sum);
        return root.val;
    }

    public static void main(String[] args) {

    }
}