leetCode-124:Binary Tree Maximum Path Sum

问题描述

给定一个二叉树，定义路径路为从某个节点开始到另一个节点经过路径上的节点数值之和。要求找出二叉树中路径和的最大值。题目链接：**点我**

样例输入输出

输入：[1,2,3]

输入代表以下的二叉树

1

/ \

2 3

输出：6

路径为：2 -> 1 -> 3

输入：[-1,2,3]

输入代表以下的二叉树

-1

/ \

2 3

输出：4

路径为：2 -> -1 -> 3

问题解法

定义pathSum 为从当前节点出发的路径和的最大值，则对于任何节点作为根节点 root 构成的二叉树，其最大的路径和为 pathSum(root.left)、pathSum(root.right)、pathSum(root.left) + root.val、pathSum(root.right) + root.val、pathSum(root.left) + pathSum(root.right) + root.val、root.val 中的最大值。对于节点 pathSum 值的求解，可以采用二叉树先序遍历的方式，在遍历过程中，不断比较并更新当前的最大路径和的值，到最后遍历结束时，程序中存储的最大路径和变量值就是求解的答案。代码如下：

/**
 * 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
{
    private int maxSum = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root)
    {
        pathSum(root);
        return maxSum;
    }
    
    private int pathSum(TreeNode root)
    {
        if (root == null)
        {
            return 0;
        }
        
        int leftPathSum = pathSum(root.left);
        int rightPathSum = pathSum(root.right);
        int tempSum = root.val;
        if (leftPathSum > 0)
        {
            tempSum += leftPathSum;
        }
        
        if (rightPathSum > 0)
        {
            tempSum += rightPathSum;
        }
        
        maxSum = Math.max(tempSum, maxSum);
        
        return Math.max(Math.max(leftPathSum, rightPathSum) + root.val, root.val);
    }
}