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.

 

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.


 To solve this problem, we can use a recursive approach. In each recursive call, we can calculate the maximum path sum that ends at the current node. This can be done by adding the value of the current node to the maximum path sum that ends at the left child of the current node and the maximum path sum that ends at the right child of the current node. The maximum path sum that ends at the current node is the maximum of the sum obtained by including the left and right child, the value of the left child, the value of the right child, and 0 (if the current node does not have any children).

We can also keep track of the maximum path sum we have seen so far. This will be the maximum of the maximum path sum ending at the current node, the maximum path sum ending at the left child of the current node, and the maximum path sum ending at the right child of the current node.

Here is the pseudocode for this algorithm:

function maxPathSum(root):
    max_sum = root.val

    function dfs(node):
        if node is null:
            return 0

        left_sum = max(0, dfs(node.left))
        right_sum = max(0, dfs(node.right))
        max_sum = max(max_sum, left_sum + right_sum + node.val)

        return max(left_sum, right_sum) + node.val

    dfs(root)

    return max_sum

This algorithm has a time complexity of O(n) where n is the number of nodes in the binary tree. This is because we visit each node in the tree exactly once in the dfs function. The space complexity is O(n) in the worst case when the binary tree is completely unbalanced, and O(log n) in the best case when the binary tree is balanced. This is because the depth of the recursive call stack is equal to the height of the binary tree.

The maxPathSum function takes in a binary tree root and returns an integer representing the maximum path sum of any non-empty path in the binary tree.

The function first initializes a variable max_sum to the value of the root node. This variable will keep track of the maximum path sum we have seen so far.

Next, the function defines a nested dfs function, which will be used to calculate the maximum path sum ending at the current node. The dfs function takes in a node node and returns an integer representing the maximum path sum ending at node.

The dfs function first checks if node is null. If node is null, the function returns 0.

Next, the function calculates the maximum path sum ending at the left and right children of node. It does this by recursively calling the dfs function on the left and right children of node and taking the maximum of the result and 0. This is because the maximum path sum ending at a child node can be 0 if the path does not include that child node.

The function then updates max_sum with the maximum of the current max_sum and the maximum path sum ending at node, which is the sum of the maximum path sums ending at the left and right children of node and the value of node.

Finally, the function returns the maximum path sum ending at node, which is the maximum of the maximum path sums ending at the left and right children of node and the value of node.

After defining the dfs function, the maxPathSum function calls the dfs function on the root node. This will calculate the maximum path sum ending at each node in the binary tree.

Finally, the maxPathSum function returns max_sum, which is the maximum path sum of any non-empty path in the binary tree.