124. Binary Tree Maximum Path Sum[Hard]

124. Binary Tree Maximum Path Sum

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Constraints:

• The number of nodes in the tree is in the range [1, 3 * 10^4].
• -1000 <= Node.val <= 1000

Example

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

思路

题解

    // 本来是赋0的，但是有可能节点都是负数
    int result = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfsMaxPathSum(root);
        return result;
    }

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

        // 如果左子树加起来的和已经小于0了，那就直接全部放弃，因为就算加上了也只会比当前值小
        int left = Math.max(dfsMaxPathSum(root.left), 0);
        // 右子树同理
        int right = Math.max(dfsMaxPathSum(root.right), 0);

        // 那么当前节点的路径最大值，就是当前值+最大左子树之和+最大右子树之和
        result = Math.max(result, root.val + left + right);

        // 但是返回的时候只能选一条路，因为还要在返回上一级
        return root.val + Math.max(left, right);
    }