二叉树中的最大路径和

题目描述

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

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

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

示例1：

1
2
3

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例2：

1
2
3

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

树中节点数目范围是 [1, 3 * $10^4$]
-1000 <= Node.val <= 1000

题解

代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int ans = Integer.MIN_VALUE;

    int oneSideMax(TreeNode root) {
        if (root == null)
            return 0;
        int left = Math.max(0, oneSideMax(root.left));
        int right = Math.max(0, oneSideMax(root.right));
        ans = Math.max(ans, left + right + root.val);
        return Math.max(left, right) + root.val;
    }

    public int maxPathSum(TreeNode root) {
        oneSideMax(root);
        return ans;
    }
}

子函数 oneSideMax(node) 采用了递归的思想，该函数用来计算二叉树中的一个节点的最大贡献值，具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。

具体的计算如下（对比代码来看，先忽略 ans = ... 的这一行）：

空节点的最大贡献值等于 0
非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）（考虑到节点的最大贡献值可能为负值，因此当子路径有负值时该子路径将被舍弃，记为0）

例如，考虑示例2的二叉树：

叶节点 9、15、7 的最大贡献值分别为 9、15、7。

非叶节点 20 的最大贡献值等于 $20+\max(15,7)=35$，节点 −10 的最大贡献值等于 $-10+\max(9,35)=25$。

上述计算过程是递归的过程，因此，对根节点调用函数 oneSideMax，即可得到每个节点的最大贡献值。

根据函数 oneSideMax得到每个节点的最大贡献值之后，如何得到二叉树的最大路径和？

对于二叉树中的一个节点，该节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值，如果子节点的最大贡献值为正，则计入该节点的最大路径和，否则不计入该节点的最大路径和。维护一个全局变量 ans 存储最大路径和，在递归过程中更新 ans 的值，最后得到的 ans 的值即为二叉树中的最大路径和。

复杂度分析

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

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

参考

链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-leetcode-/
来源：力扣（LeetCode）