Leetcode 124. 二叉树中的最大路径和

146 阅读1分钟

给定一个非空二叉树,返回其最大路径和。

本题中,路径被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。

示例 1:

输入:[1,2,3]

   1
  / \
 2   3

输出:6

示例 2:

输入:[-10,9,20,null,null,15,7]

-10 /
9 20 /
15 7

输出:42

思考地图 1 递归采用从下而上模拟算法, 这题主要是不知道如何避免在节点的左子树或者右子树的节点被当做节点,或者换句话说如果一个节点作为根节点,那么它的左子树中的节点必须不能同时包括左子树和右子树,它的右子树的节点不能同时包括左子树和右子树 这里的方法是采用自底向上,要么返回 0,要么返回节点和它的左子树或者节点和它的右子树

算法时间复杂度 O(n),空间复杂度 O(1)

/**
 * @param {TreeNode} root
 * @return {number}
 */
export default (root) => {
  function getMaxSum(node) {
    if (!node) return 0;
    let leftSum = getMaxSum(node.left);
    let rightSum = getMaxSum(node.right);
    // 从下而上找到最大的
    max = Math.max(max, node.val + leftSum + rightSum);
    // 采用从下而上,如果小于0,则最少返回0,然后返回该节点和左子树或者该节点和右子树的和
    return Math.max(leftSum + node.val, rightSum + node.val, 0);
  }
  let max = -Number.MAX_VALUE;
  getMaxSum(root);
  return max;
};