# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    maxVal=0
    def getMaxPath(self,root):
        if root is None:
            return 0
        l=self.getMaxPath(root.left)
        r=self.getMaxPath(root.right)
        single=max(max(l,r)+root.val,root.val)
        val=max(l+r+root.val,single)
        if val>self.maxVal:
            self.maxVal=val
        return single
            
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.maxVal=-sys.maxsize
        if root is None:
            return 0
        value=self.getMaxPath(root)
        return self.maxVal
        
        

b55c80954bda50866e0753124db2891475959a14
class Solution:
    <mask token>
    <mask token>
    <mask token>

class Solution:
    <mask token>

    def getMaxPath(self, root):
        if root is None:
            return 0
        l = self.getMaxPath(root.left)
        r = self.getMaxPath(root.right)
        single = max(max(l, r) + root.val, root.val)
        val = max(l + r + root.val, single)
        if val > self.maxVal:
            self.maxVal = val
        return single
    <mask token>

class Solution:
    <mask token>

    def getMaxPath(self, root):
        if root is None:
            return 0
        l = self.getMaxPath(root.left)
        r = self.getMaxPath(root.right)
        single = max(max(l, r) + root.val, root.val)
        val = max(l + r + root.val, single)
        if val > self.maxVal:
            self.maxVal = val
        return single

    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.maxVal = -sys.maxsize
        if root is None:
            return 0
        value = self.getMaxPath(root)
        return self.maxVal

class Solution:
    maxVal = 0

    def getMaxPath(self, root):
        if root is None:
            return 0
        l = self.getMaxPath(root.left)
        r = self.getMaxPath(root.right)
        single = max(max(l, r) + root.val, root.val)
        val = max(l + r + root.val, single)
        if val > self.maxVal:
            self.maxVal = val
        return single

    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.maxVal = -sys.maxsize
        if root is None:
            return 0
        value = self.getMaxPath(root)
        return self.maxVal

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    maxVal=0
    def getMaxPath(self,root):
        if root is None:
            return 0
        l=self.getMaxPath(root.left)
        r=self.getMaxPath(root.right)
        single=max(max(l,r)+root.val,root.val)
        val=max(l+r+root.val,single)
        if val>self.maxVal:
            self.maxVal=val
        return single
            
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.maxVal=-sys.maxsize
        if root is None:
            return 0
        value=self.getMaxPath(root)
        return self.maxVal
        
        
