leetcode-124. Binary Tree Maximum Path Sum

本文主要是介绍leetcode-124. Binary Tree Maximum Path Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

leetcode-124. Binary Tree Maximum Path Sum

题目：

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,
   1/ \2   3
Return 6.

这题比较有意思。这里计算的是所有可能路径的和。我一开始计算的是两个叶节点之间的最大和

这题显然是需要迭代的，但是每次迭代中却需要进行很多次比较，所以对于结果我使用了域。

针对一个节点需要比较这几个，
其左子节点对应的最大值，
其右子节点对应的最大值，
其从左子节点-根节点-右节点之和，
其从左子节点-根节点之和，
其根节点-右节点之和，
以及ret。

这几个值之间的最大值。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
public class Solution {private int ret = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {if(root==null) return Integer.MIN_VALUE;findmaxpath(root);return ret;}private int findmaxpath(TreeNode node){if(node == null) return 0;int left = Math.max(0, findmaxpath(node.left));int right = Math.max(0, findmaxpath(node.right));ret = Math.max(ret, left + right + node.val);return node.val + Math.max(left,right);}
}