# Problem 124: Binary Tree Maximum Path Sum

> <https://leetcode.com/problems/binary-tree-maximum-path-sum/>

## 思路

![](/files/-Lpv9wbxg_ouFpX6JG3B)

1. singlePath: 从root往下走到任意点的最大路径，这条路径可以不包含任何点; maxPath: 从树中任意到任意点的最大路径，这条路径至少包含一个点
2. 分治思想：首先一分为二，left，right。然后分别再考虑他们的singlePath 和 maxPath。

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxPathSum(TreeNode root) {
        ResultType result = helper(root);
        return result.maxPath;
    }

    public class ResultType {
        int singlePath, maxPath;
        public ResultType (int singlePath, int maxPath) {
            this.singlePath = singlePath;
            this.maxPath = maxPath;
        }
    }

    private ResultType helper(TreeNode root) {
        if (root == null) {
            return new ResultType(0, Integer.MIN_VALUE);
        }

        //divide
        ResultType left = helper(root.left);
        ResultType right = helper(root.right);

        //conquer
        int singlePath = Math.max(left.singlePath, right.singlePath) + root.val;
        singlePath = Math.max(singlePath, 0);

        int maxPath = Math.max(left.maxPath, right.maxPath);
        maxPath = Math.max(maxPath, left.singlePath + right.singlePath + root.val);

        return new ResultType(singlePath, maxPath);
    }
}
```

## 易错点

1. 边界条件

   ```java
   if (root == null) {
    return new ResultType(0, Integer.MIN_VALUE);
   }
   ```

   最小值用的是`Integer.MIN_VALUE`而不是 Math
2. singlePath

   ```java
   int singlePath = Math.max(left.singlePath, right.singlePath) + root.val;
   singlePath = Math.max(singlePath, 0);
   ```

   首先，左右两条道选一个大的，再带上root；其次，singlePath**有可能是一负数**
3. maxPath

   ```java
   int maxPath = Math.max(left.maxPath, right.maxPath);
   maxPath = Math.max(maxPath, left.singlePath + right.singlePath + root.val);
   ```

   同理，首先，左右两条道选一个大的；其次考虑左右“单打”和图中“绕圈”哪个更大。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://liuyang89116.gitbook.io/my-leetcode-book/chapter_3_binary_tree_bfs-_dfs/problem_124_binary_tree_maximum_path_sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.