// MARK: - 124 Binary Tree Maximum Path Sum

func maxPathSum(_ root: TreeNode?) -> Int {
    var res = root?.val


    // Возвращаем максимальный путь без последующего разделения на ноды
    func dfs(root: TreeNode?) -> Int {
        if root == nil {return 0}

        var leftMax = dfs(root: root?.left)
        var rightMax = dfs(root: root?.right)
        // Чтобы не считать отрицательные
        leftMax = max(leftMax, 0)
        rightMax = max(rightMax, 0)

        res = max(res!, root!.val + leftMax + rightMax)
        // Можем выбрать только один6 так как иначе мы разделяем, а это не тот случай
        return root!.val + max(leftMax, rightMax)
    }

    dfs(root: root)
    return res!
}