# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.maxVal = float('-inf')
        self.nodeMax(root)
        return self.maxVal
    def nodeMax(self, node) -> int:
        if node == None:
            return float('-inf')
        left = self.nodeMax(node.left)
        right = self.nodeMax(node.right)
        nodeMax = max(node.val + left, node.val + right, node.val)
        self.maxVal = max(self.maxVal, nodeMax, node.val + left + right)
        return nodeMax

/**
 * 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;
 *     }
 * }
 */
int max = -10000;
public int maxPathSum(TreeNode root) {
    maxWithChild(root);
    return max;
}
public int maxWithChild(TreeNode root) {
    if (root == null) return -10000;
    int left = maxWithChild(root.left);
    int right = maxWithChild(root.right);
    int nodeMax = Math.max(root.val, root.val + Math.max(left, right));
    max = Math.max(max, Math.max(nodeMax, root.val + left + right));
    return nodeMax;
}