hardTrees

Binary Tree Maximum Path Sum

Find the maximum sum of a nonempty path in a binary tree. A path follows parent-child edges and cannot visit a node twice; it may start and end anywhere.

LeetCode ↗

Work through the cases

3 examples

Input notation

A binary tree in level order on one line, using null for missing children. Omit trailing nulls; use null for an empty tree. The tree is nonempty.

Expected result

The maximum path sum.

Case 1

Input

-10 9 20 null null 15 7

Expected output

Case 2

Input

-3

Expected output

-3

Case 3

Input

-2 -1 -3

Expected output

-1

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

A path may start anywhere, need not pass the root, and may bend at a node to take both children. Enumerating paths is impossible at n ≤ 3 × 10^4. The value a node can pass upward is its value plus the better non-negative child chain. The sum that uses both children only updates the global answer and cannot propagate. Negative contributions are dropped by taking \max(0, × ) before returning.

When thinking about the classic routine of recursion problems in binary trees, we consider:

1. Termination condition (when to terminate recursion) 2. Recursively process the left and right subtrees 3. Merge the calculation results of the left and right subtrees

For this problem, we design a function dfs(root), which returns the maximum path sum of the binary tree with root as the root node.

The execution logic of the function dfs(root) is as follows:

If root does not exist, then dfs(root) returns 0;

Otherwise, we recursively calculate the maximum path sum of the left and right subtrees of root, denoted as left and right. If left is less than 0, then we set it to 0, similarly, if right is less than 0, then we set it to 0.

Then, we update the answer with root.val + left + right. Finally, the function returns root.val + \max(left, right).

In the main function, we call dfs(root) to get the maximum path sum of each node, and the maximum value among them is the answer.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int ans = -1001;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = Math.max(0, dfs(root.left));
        int right = Math.max(0, dfs(root.right));
        ans = Math.max(ans, root.val + left + right);
        return root.val + Math.max(left, right);
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.