Leetcode - 124. 二叉树中的最大路径和

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    // maxPathSum表示当前找到的最大路径和
    private int maxPathSum = Integer.MIN_VALUE;

    //     -10        |   假设给定的二叉树如右图所示，那么我们可以对它进行后序遍历：
    //     / \        |   第一个节点是9，是叶子节点，此时更新maxPathSum为9，并将9告知给父节点
    //    9   20      |   第二个节点是15，是叶子节点，此时更新maxPathSum为15，并将15告知给父节点
    //       /  \     |   第三个节点是7，是叶子节点，7比15小，因此不更新maxPathSum，并将7告知给父节点
    //      15   7    |   第四个节点是20，它的子节点返回了15和7，加起来为42，因此更新maxPathSum为42，并将35告知给父节点
    //  -----------   |   第五个节点为-10，它的子节点返回了9和35，加起来为34，此时不更新maxPathSum，并将25返回
    // 每个子节点都会向其父节点返回一个值，它代表如果父节点要将子节点纳入连接的话，父节点能获得的最大收益
    public int maxPathSum(TreeNode root) {
        maxPathSumInternal(root);
        return maxPathSum; 
    }

    // 搜索二叉树中的最大路径和；如果最大路径和大于maxPathSum，则更新maxPathSum
    // 该方法的返回值用于告知root的父节点，如果将root节点纳入连接，它能获得的最大收益
    // 注意，连接是不存在分叉的，因此将root节点纳入连接时，最多只能再纳入root节点的其中一个子节点
    private int maxPathSumInternal(TreeNode root) {
        
        // 空节点不能纳入连接，因此直接返回Integer.MIN_VALUE（或任意非正数）即可
        // root的父节点在看到maxPathSumInternal(root)返回非正数后，自然就不会把root纳入连接了
        if (root == null) {
            return Integer.MIN_VALUE;
        }
        
        // 如果是叶子节点，那么该节点本身就是一条路径，路径和为root.val
        // 并且，如果父节点将本节点纳入连接，则其能获得的最大收益也是root.val
        if (root.left == null && root.right == null) {
            maxPathSum = Math.max(maxPathSum, root.val);
            return root.val;
        }

        // 如果不是叶子节点，则继续搜索左右子树
        int left = maxPathSumInternal(root.left);
        int right = maxPathSumInternal(root.right);
        
        // 如果左/右子树的最大收益大于0，则将左/右子树纳入连接
        // 此时我们就找到了一个局部最优解：root.val + Math.max(left, 0) + Math.max(right, 0)
        maxPathSum = Math.max(maxPathSum, root.val + Math.max(left, 0) + Math.max(right, 0));
            
        // 本方法的返回值表示如果将本节点纳入连接，父节点能获得的最大收益
        // 由于连接不能分叉，所以这条连接最多只能经过本节点的一个子节点，这就需要在left和right中进行取舍了：
        // 1. 如果left和right都小于0，则不要连接左/右节点，直接返回root.val
        // 2. 否则，left和right哪个更大，就应该连接对应的那个节点
        return root.val + Math.max(0, Math.max(left, right));
    }
}