一、写在前面
它的难，并不在于写出 DFS，而在于：

1. 路径可以不经过根；  
2. 路径可以只含一个节点；  
3. 节点值可能为负；

二、题意再翻译

给定一棵二叉树，找出任意一条节点序列，使得：

- 相邻节点必须父子相连；  
- 同一节点至多出现一次；  
- 序列和最大。

返回这个最大和。

注意：路径可以从任意节点出发，到任意节点结束，不必经过根。

三、示例热身

例 1  

      1
     / \
    2   3
```

最优路径：2 → 1 → 3，和 = 6。

例 2  

```
      -10
      /  \
     9   20
         / \
        15  7

最优路径：15 → 20 → 7，和 = 42。

---

四、思路拆解：后序 DFS + 全局变量

1. 定义“贡献值”

对于当前节点 `node`，它向上层父亲能做出的最大单边贡献是：  

```
node.val + max(0, 左子树贡献, 右子树贡献)
```

如果左/右子树贡献为负，还不如不走那边（取 0）。

2. 拼出“跨越”路径

以 `node` 为拐点的一条完整路径和：  

```
node.val + max(0, left) + max(0, right)
```

这条路径不能再往上延伸，否则会分叉。

3. 全局打擂台

用全局变量 `maxSum` 实时更新第 2 步算出的值。

初始设为 `Integer.MIN_VALUE`，防止所有节点都是负数。

4. 返回什么？

只能返回单边最大贡献给父节点，否则就分叉了。

---

五、代码时间（Java）

```java
class Solution {
    private int maxSum = Integer.MIN_VALUE;

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

    private int dfs(TreeNode node) {
        if (node == null) return 0;

        int left  = Math.max(dfs(node.left),  0); // 负贡献直接丢弃
        int right = Math.max(dfs(node.right), 0);

        int path = node.val + left + right; // 以 node 为拐点的完整路径
        maxSum = Math.max(maxSum, path);

        return node.val + Math.max(left, right); // 单边贡献
    }
}
```

---

六、复杂度分析

- 时间：每个节点仅访问一次 → O(N)  
- 空间：递归栈最深树高 → O(H)（H 为树高，最坏链式退化成 O(N)）

---

七、常见坑位提醒

1. 全局变量必须初始化为 `Integer.MIN_VALUE`，否则全负树会错。  
2. 左右子树贡献为负时，要果断取 0，表示“不选”。  
3. 返回给父节点的只能是单边，不能同时带左右两边。  

---

八、 debug 小技巧

打印每次 `path` 与 `maxSum`，肉眼追踪第一棵负树：

```
node = -10, path = 42, maxSum = 42
```

看到 `maxSum` 一次性从负值跳到 42，就知道拐点在 `-10` 的右子树，稳！

---