力扣链接：124.二叉树中的最大路径和

难度：⭐⭐⭐

解题关键词：二叉树、后序遍历

解题思路：根据深度优先递归遍历，不断计算最大值，最大值就是当前节点的值 + 左子树最大值 + 右子树最大值，当前节点的最大路径和是当前节点的值加左右节点中最大的值。

function maxPathSum(root: TreeNode | null): number {
  // 结果，设置为最小值
  let result = -Infinity;

  const dfs = (root: TreeNode | null) => {
    // 如果节点为空，那么返回0
    if (root === null) return 

    // 计算左子树中最大路径和
    const leftMax = Math.max(0, dfs(root.left));
    // 计算右子树中最大路径和
    const rightMax = Math.max(0, dfs(root.right));

    // 最大值就是当前节点的值 + 左子树最大值 + 右子树最大值
    result = Math.max(result, root.val + leftMax + rightMax);

    // 当前节点的最大路径和是当前节点的值加左右节点中最大的值
    return root.val + Math.max(leftMax, rightMax);
  };

  dfs(root);

  return result;
}