题目：

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

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

?

思路：递归

分为三部分，根节点，左子树，右子树。

?

三要素：

方法名：helper

参数列表：(TreeNode node)

返回值：int[] (长度为2，下标零记录node属最大路径和，下标1记录连接node的最大路径和)

?

内容：

第一部分：终止条件，当node为空，返回res数组，数组内值赋为Integer.MIN_VALUE。

第二部分：分别递归node节点左、右子树得到 left数组，right数组。

第三部分：res数组保存连接node树的最大路径和，以及left与right数组中存储的最大路径和中的最大值。

第四部分：返回res数组。

完善细节即刻。

?

代码实现：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public final int MIN = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        return helper(root)[0];
    }
    public int[] helper(TreeNode node){
        if(node == null){
            int[]res =  new int[2];
            res[0] = MIN;
            res[1] = MIN;
            return res;
        }
        int[] left = helper(node.left);
        int[] right = helper(node.right);
        int[] res = new int[2];
        //含根节点只过一条分支的最大值
        res[1] += node.val;
        int max = 0;
        max = left[1]>right[1]?left[1]:right[1];
        res[1] += max>0?max:0;
        //最大值，（两侧最大值中最大值，过根节点与两侧含根节点最大值的最大值）
        if(isNull(left)&&isNull(right)){
            res[0] = res[1];
        }else{
            //两侧最大值中最大值
            int p1 = left[0]>=right[0]?left[0]:right[0];
            //过根节点与两侧含根节点最大值的最大值
            int p2 = left[1]>0?left[1]:0;
            p2 += right[1]>0?right[1]:0;
            p2 += node.val;
            res[0] = p1>p2?p1:p2;
        }
        //System.out.println("节点:"+node.val+"的最大值:"+res[0]+"一条最大值："+res[1]);
        return res;
    }
    public boolean isNull(int[] a){
        return a[0]==MIN&&a[1]==MIN;
    }
}

LeetCode 124 二叉树中最大路径和

原文：https://www.cnblogs.com/deusjin/p/13172245.html