【算法题-困难】二叉树的最大路径和

困难算法题，二叉树的最大路径和，使用 JavaScript 语言编写

题目

二叉树中的“路径”被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。

“路径和”是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其最大路径和。

输入格式

树上的节点数满足 0 <= n <= 1000, 每个节点的值满足 -1000 <= val <= 1000

（注：null节点的左右叶子不会再打印 null）

输出格式

输出最大路径的和

输入样例

-10,9,20,null,null,15,7

输出样例

42

分析

要实现这个算法，我们可以使用递归的方法来遍历二叉树，并在每个节点计算包含该节点的最大路径和。我们需要一个辅助函数来计算从当前节点出发的最大路径和，同时更新全局最大路径和。

解答

// 这是题目要求的输入格式
let inputs = `
-10,9,20,null,null,15,7
`;
const nodes = inputs.trim().split(',').map(num => isNaN(num) ? null : parseInt(num));

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function buildTree(nodes) {
  if (!nodes.length) return null;
  const root = new TreeNode(nodes[0]);
  const queue = [root];
  let i = 1;
  while (i < nodes.length) {
    const current = queue.shift();
    if (nodes[i] !== null) {
      current.left = new TreeNode(nodes[i]);
      queue.push(current.left);
    }
    i++;
    if (i < nodes.length && nodes[i] !== null) {
      current.right = new TreeNode(nodes[i]);
      queue.push(current.right);
    }
    i++;
  }
  return root;
}

function maxPathSum(root) {
  let maxSum = -Infinity;

  function maxGain(node) {
    if (node === null) {
      return 0;
    }

    // 递归计算左右子树的最大路径和
    const leftGain = Math.max(maxGain(node.left), 0);
    const rightGain = Math.max(maxGain(node.right), 0);

    // 计算经过当前节点的路径和
    const currentPathSum = node.val + leftGain + rightGain;

    // 更新全局最大路径和
    maxSum = Math.max(maxSum, currentPathSum);

    // 返回从当前节点出发的最大路径和, 因为如果当前节点不是最终路径的根节点, 那么只能选择左子树或者右子树，不能同时选择
    return node.val + Math.max(leftGain, rightGain);
  }

  maxGain(root);
  return maxSum;
}

// 示例
const root = buildTree(nodes);
console.log(maxPathSum(root)); // 输出 42