1. 题目描述

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

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

示例 1：

  1. 输入：[1,2,3]
  2.        1
  3.       / \
  4.      2   3
  5. 输出：6

示例 2：

  1. 输入：[-10,9,20,null,null,15,7]
  2.    -10
  3.    / \
  4.   9  20
  5.     /  \
  6.    15   7
  7. 输出：42

2. 解题思路

对于这道题目，我们可以使用递归遍历二叉树，我们需要的是最大的路径和，所以某个节点左右子树路径和和这个节点的值的和的最大值就是我们要求的解。

需要注意：

  • 一条从父节点延伸下来的路径，只能进入左子树或者右子树，不能同时进入左右子树。
  • 只有在最大贡献值大于 0 时，才会选取对应子节点。

复杂度分析：

  • 时间复杂度：O(N)，其中 N 是二叉树中的节点个数。对每个节点访问不超过 2 次。

  • 空间复杂度：O(N)，其中 N 是二叉树中的节点个数。空间复杂度主要取决于递归调用层数，最大层数等于二叉树的高度，最坏情况下，二叉树的高度等于二叉树中的节点个数。

    3. 代码实现

    1. /**
    2. * Definition for a binary tree node.
    3. * function TreeNode(val) {
    4. *     this.val = val;
    5. *     this.left = this.right = null;
    6. * }
    7. */
    8. /**
    9. * @param {TreeNode} root
    10. * @return {number}
    11. */
    12. var maxPathSum = function(root) {
    13.   let sum = Number.MIN_SAFE_INTEGER
    15.   const dfs = (root) => {
    16.       if(!root){
    17.           return 0
    18.       }
    19.       // 计算左右子树的最大路径和
    20.       const left = dfs(root.left)
    21.       const right = dfs(root.right)
    23.       // 计算总的最大路径和
    24.       const maxSum = left + root.val + right
    25.       sum = Math.max(sum, maxSum)
    27.       // 返回当前计算出的最大路径
    28.       const max = root.val + Math.max(left, right)
    29.       return max < 0 ? 0 : max
    30.   }
    31.   dfs(root)
    32.   return sum
    33. };

    4. 提交结果

    image.png