Please solve in Python Coding Language. Thank you!

3) Binary Tree Maximum Path Sum A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node's values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty path. Explanation: The optimal path is 2>13 with a path sum of 2+1+3= 6. Example 2: Input: root =[10,9,20, nul1, nul1, 15, ] Output: 42 Explanation: The optimal path is 15207 with a path sum of 15+20+7 =42 Constraints: - The number of nodes in the tree is in the range [1,3104]. - 1000