LeetCode-Binary-Tree-Maximum-Path-Sum

Problem Description

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

1
2
3

  1
 / \
2   3

Return 6.

problem link:
https://leetcode.com/problems/binary-tree-maximum-path-sum/description/

Solution

public class Solution {
    int maxValue;
    
    public int maxPathSum(TreeNode root) {
        maxValue = Integer.MIN_VALUE;
        maxPathDown(root);
        return maxValue;
    }
    
    private int maxPathDown(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(0, maxPathDown(node.left));
        int right = Math.max(0, maxPathDown(node.right));
        maxValue = Math.max(maxValue, left + right + node.val);
        return Math.max(left, right) + node.val;
    }
}

解题思路

每一个结点可以选和不选，处理方法就是：int left = Math.max(0, maxPathDown(node.left));，其中的 Math.max(0, x)，当取值为 0 时就是不取这个结点。

全局变量 maxValue 就覆盖了子树中的 ^ 这种类型，例如子树如下：

1
2
3

       x
   a     y
b    c

则 b->a->c 这种路径的最大值被 maxValue 保存了。而 b->a->x->y 这种经过根节点的路径被 Math.max(left, right) + node.val; 覆盖了。