LeetCode: Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

---

For a binary tree, the max sum path may be one of the following situations:

1. The path only contains the root node.

2. The path contains the root node and its left subtree path.

3. The path contains the root node and its right subtree path.

4. The path contains the root node, its left subtree path and right subtree path.

5. The path is from its left subtree path, and doesn't include root node.

6. The path is from its right subtree path, and doesn't include root node.

C++ Code:

/*
 * func: binary_tree_max_path_sum_helper
 * goal: helper function to find the maximum value
 * @param root: root node of the tree
 * @param max_sum: current max sum
 * return: max sum passing current node
 */
int binary_tree_max_path_sum_helper(TreeNode *root, int &max_sum){
    if(root == nullptr){
        return 0;
    }
    
    //Get the maximum value the path of which includes root.left
    int left_max = binary_tree_max_path_sum_helper(root->left, max_sum);
    //Get the maximum value the path of which includes root.left
    int right_max = binary_tree_max_path_sum_helper(root->right, max_sum);
    //Get the maximum value the path of which includes root node
    int current_max = max(root->val, max(root->val + left_max, root->val + right_max));
    //Update global maximum value
    max_sum = max(max(current_max, root->val + left_max + right_max), max_sum);
    
    return current_max;
}
 
/*
 * func: binary_tree_max_path_sum
 * goal: find the maximum path sum, the path may start and end at any node
 * @param root: root node of the tree
 * return: maximum path sum
 */
int binary_tree_max_path_sum(TreeNode *root){
    if(root == nullptr){
        return 0;
    }
    int max_sum = root->val;
    binary_tree_max_path_sum_helper(root, max_sum);
    return max_sum;
}

Python Code:

# func: find the maximum path sum
# @param root: root node of the tree
# @return: maximum value
def max_path_sum(self, root):
    if not root:
        return 0
    self.max_value = root.val
    def max_path_sum_helper(node):
        if not node:
            return 0
        left_value = max_path_sum_helper(node.left)
        right_value = max_path_sum_helper(node.right)

        current_value = max(node.val, node.val+left_value, node.val+right_value)
        self.max_value = max(self.max_value, current_value, node.val + left_value + right_value)

        return current_value
    max_path_sum_helper(root)
    return self.max_value