Leetcode #124 | #Hard | [[Деревья]] | [[DFS]]
## Идея
dfs + отбрасываем отрицательные пути
## Big-O
- Время ```O(N)```
- Память  ```O(H)```
N - кол-во узлов, H -высота дерева
## Код
```Java
class Solution {
    private int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return res;
    }
    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(0, dfs(node.left)); // путь в левой ветке
        int right = Math.max(0, dfs(node.right)); // путь в правой ветке
        res = Math.max(res, node.val + left + right); // итоговый путь через вершину
        return node.val + Math.max(left, right); // максимальный путь вниз
    }
}
```