package Leetcode.Trees;

/**
 * @author zhengstars
 * @date 2024/04/19
 */
public class BinaryTreeMaximumPathSum {
    // A variable to keep the maximum path sum
    private static int maxSum = Integer.MIN_VALUE;

    // The main function to find the maximum path sum.
    public static int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    // A helper function to find the maximum gain of each node.
    private static int maxGain(TreeNode node) {
        // Base case: if the node is null, return 0
        if (node == null) {
            return 0;
        }

        // Recursive case
        // Calculate the maximum sum of the left and right subtrees. If a subtree sum is negative, we ignore it and return 0.
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // Check if the price of the new path would be greater than the current maxSum
        int priceNewPath = node.val + leftGain + rightGain;

        // Update the maxSum if the price of the new path is greater
        maxSum = Math.max(maxSum, priceNewPath);

        // Return the max gain if we would continue the same path
        return node.val + Math.max(leftGain, rightGain);
    }

    public static void main(String[] args) {
        // Test cases
        TreeNode test1 = new TreeNode(1, new TreeNode(2), new TreeNode(3));
        System.out.println(maxPathSum(test1));  // output: 6

        TreeNode test2 = new TreeNode(-10, new TreeNode(9),
                new TreeNode(20, new TreeNode(15), new TreeNode(7)));
        System.out.println(maxPathSum(test2));  // Output: 42
    }
}