LeetCode //C - 124. Binary Tree Maximum Path Sum

124. 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.
 

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.

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Constraints:

• The number of nodes in the tree is in the range [$1,3\ast 10^4$]
• -1000 <= Node.val <= 1000

From: LeetCode
Link: 124. Binary Tree Maximum Path Sum

---

Solution:

Ideas：

Overview:
The problem is to find the maximum path sum in a binary tree. A “path” here means any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Approach:
To solve this problem, we perform a post-order traversal of the tree. For each node, we calculate two things:

1. The maximum path sum considering the current node as an endpoint.
2. The maximum path sum that could be formed using the current node, which might include paths from its left and/or right child.

The reason we need both values is that while the first one (endpoint value) helps us build the path sum for the parent node, the second value (including the current node) helps us track the global maximum path sum across the tree.

Code Explanation:

1. helper function: This is a recursive function that traverses the binary tree in a post-order manner. It calculates the maximum path sum for each node and updates the global maximum path sum.

2. globalMax: This variable keeps track of the maximum path sum encountered so far across the entire tree.

3. leftMax and rightMax: For each node, we calculate the maximum path sum for its left child and right child.

4. maxSingle: This represents the maximum path sum considering the current node as an endpoint. This is calculated as the maximum of:

• The node’s value itself.
• The node’s value + maximum path sum of the left child.
• The node’s value + maximum path sum of the right child.

5. maxTop: This represents the maximum path sum that could be formed using the current node. This is calculated as the maximum of:

• maxSingle (as explained above).
• The path sum considering both left and right children + the current node’s value.

6. globalMax update: For each node, we update the globalMax to be the maximum of the current globalMax and maxTop.

7. Returning from helper function: We return maxSingle because this represents the maximum value that can be used to form a path sum for the current node’s parent.

8. maxPathSum function: This function initializes the globalMax to the smallest possible integer value and then calls the helper function to traverse the tree and find the maximum path sum. Finally, it returns the globalMax.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int helper(struct TreeNode* root, int* globalMax) {
    if (!root) {
        return 0;
    }

    int leftMax = helper(root->left, globalMax);
    int rightMax = helper(root->right, globalMax);

    int maxSingle = fmax(fmax(leftMax, rightMax) + root->val, root->val);
    int maxTop = fmax(maxSingle, leftMax + rightMax + root->val);

    *globalMax = fmax(*globalMax, maxTop);

    return maxSingle;
}

int maxPathSum(struct TreeNode* root) {
    int globalMax = INT_MIN;
    helper(root, &globalMax);
    return globalMax;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29